This paper introduces a class of algorithms for solving general linear systems and eigenvalue problems using randomized dimension reduction techniques. These algorithms combine subspace projection methods, such as GMRES and Rayleigh–Ritz, with fast randomized sketching to accelerate the solution process. The key idea is to incorporate nontraditional bases for the approximation subspace, which are easier to construct. When the basis is numerically full rank, the new algorithms achieve similar accuracy to classic methods but with faster computation and potentially less storage. Numerical experiments demonstrate significant speedups over optimized MATLAB routines, including a 70× speedup over `gges` and a 10× speedup over `eigs`. The paper focuses on two main applications: solving linear systems and eigenvalue problems. For linear systems, the algorithms use sketching to reduce the dimension of the problem and then apply the GMRES method. For eigenvalue problems, the algorithms use sketching to solve the Rayleigh–Ritz problem, which is derived from the original eigenvalue problem. Both methods benefit from the use of nonorthogonal bases, which can be constructed efficiently using techniques like the $k$-truncated Arnoldi process. The paper also discusses the advantages and limitations of the proposed methods, including their robustness and the need for efficient basis constructions. It provides a rigorous treatment of sketching for least-squares problems and detailed analyses of the sGMRES and sRR algorithms. Computational experiments confirm the effectiveness and efficiency of the proposed algorithms, showing significant speedups over traditional methods in various scientific computing and optimization tasks.This paper introduces a class of algorithms for solving general linear systems and eigenvalue problems using randomized dimension reduction techniques. These algorithms combine subspace projection methods, such as GMRES and Rayleigh–Ritz, with fast randomized sketching to accelerate the solution process. The key idea is to incorporate nontraditional bases for the approximation subspace, which are easier to construct. When the basis is numerically full rank, the new algorithms achieve similar accuracy to classic methods but with faster computation and potentially less storage. Numerical experiments demonstrate significant speedups over optimized MATLAB routines, including a 70× speedup over `gges` and a 10× speedup over `eigs`. The paper focuses on two main applications: solving linear systems and eigenvalue problems. For linear systems, the algorithms use sketching to reduce the dimension of the problem and then apply the GMRES method. For eigenvalue problems, the algorithms use sketching to solve the Rayleigh–Ritz problem, which is derived from the original eigenvalue problem. Both methods benefit from the use of nonorthogonal bases, which can be constructed efficiently using techniques like the $k$-truncated Arnoldi process. The paper also discusses the advantages and limitations of the proposed methods, including their robustness and the need for efficient basis constructions. It provides a rigorous treatment of sketching for least-squares problems and detailed analyses of the sGMRES and sRR algorithms. Computational experiments confirm the effectiveness and efficiency of the proposed algorithms, showing significant speedups over traditional methods in various scientific computing and optimization tasks.