In this work, we present the comprehensive rounding error analysis of RCLUPPr proposed in \cite{RCLUPP}, which is a novel randomized CholeskyQR-type algorithm performing LU decomposition with partial pivoting (LUPP decomposition) directly on the tall-skinny $X\in\mathbb{R}^{m\times n}$ with $m \ge n$ and $\mbox{rank}(X)=n$. In contrast to the existing RCLUPP in \cite{RCLUPP}, which applies matrix sketching before LUPP decomposition, RCLUPPr places LUPP decomposition as a preconditioning step first, significantly reducing error propagation. Our analysis rigorously proves that RCLUPPr enjoys markedly better applicability to the ill-conditioned matrices than the existing CholeskyQR-type algorithms and remains stable and accurate in the mixed-precision arithmetic. We further propose practical acceleration strategies in the real implementations of RCLUPPr. Extensive numerical experiments on the real-world problems confirm the theoretical results in this work, demonstrating the robustness and practicality of RCLUPPr in the single, double, and the mixed-precision architecture.
The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind...
Adaptive optimization methods have received considerable attention in recent years due to their strong empirical performance. However, they generally require maintaining a preconditioning matrix, which incurs prohibitive computational overhead in large-scale applications. To address these limitations, we investigate th...
Si-Fan Yang, Yuanyu Wan, Yi-Bo Wang et al.· 0 citations
In this work, we develop sketched variants of subspace iteration and TraceMIN, called sSI and sTraceMIN, for real symmetric eigenvalue problems by combining basis whitening with the sketched Rayleigh-Ritz (sRR) procedure. The nonsymmetric projected matrix in sRR may have nonreal eigenpairs, leading to complex arithmeti...
The spectral limited-memory preconditioner (sLMP) clusters leading eigenvalues of symmetric positive definite matrices to accelerate conjugate gradient (CG) convergence. In practice, the cluster point is often chosen to be unity. In some cases, however, this choice can fail to accelerate convergence relative to unpreco...
Hisham G. Elzayyadi, Jemima M. Tabeart· 0 citations
State‐of‐the‐art iterative refinement (IR)‐based methods mainly employ
LU
factorization to construct preconditioners, which severely limits their applicability to sparse linear systems due to excessive memory overhead. In order to address such issues, we exploit incomplete
LU
(
ILU
) factorization as a precon...
Hai-Bin Sun, Hai-Peng Yang, Yan-Fei Jing et al.· Numerical Linear Algebra wit...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
