Source-linked AI summary
A Novel Randomized XR-Based Preconditioned CholeskyQR Algorithm
Yuwei Fan, Yixiao Guo, Ting Lin
TL;DR
CholeskyQR is efficient for tall-and-skinny matrices but can be numerically unstable for ill-conditioned inputs. The paper proposes randomized LU- and QR-based preconditioners, reporting stability and runtime advantages for its methods. Its analysis also identifies cases where the sampling requirement can become impractical.
Problem
CholeskyQR is communication- and computation-efficient for tall-and-skinny matrices, but the condition number of A^T A is cond(A)^2, making it numerically unstable for ill-conditioned inputs.
Source: §1 · p. 2Method
The method factors a randomly chosen submatrix using LU or QR, uses the resulting upper-triangular factor's inverse to precondition A, and applies CholeskyQR to the preconditioned matrix.
Source: §2.2 · p. 5Results
Among stable methods, randomized LU/QR-CholeskyQR have the best runtime; at n=100 and m=100,000, CholeskyQR2 takes 24% more time than rQR-CholeskyQR.
Source: §4.3 · pp. 14–15Takeaways & Limitations
The framework can identify rank deficiency with high probability, which matters because the paper says only direct QR methods could work for rank-deficient systems.
Source: §1 · p. 2When Q = [I, 0]^T, the concentration condition requires l = O(m log n log δ^-1), which the paper says can become impractical as n grows.
Source: §3 · p. 10
Abstract
from arXiv · showhide
CholeskyQR is a simple and fast QR decomposition via Cholesky decomposition, while it has been considered highly sensitive to the condition number. In this paper, we provide a randomized preconditioner framework for CholeskyQR algorithm. Under this framework, two methods (randomized LU-CholeskyQR and randomized QR-CholeskyQR) are proposed and discussed. We prove the proposed preconditioners can effectively reduce the condition number, which is also demonstrated by numerical tests. Abundant numerical tests indicate our methods are more stable and faster than all the existing algorithms and have good scalability.
1. Introduction.
The paper targets tall-and-skinny QR, where CholeskyQR is efficient but sensitive to conditioning, and proposes randomized preconditioning as an alternative. It positions this approach against existing QR methods and emphasizes reduced cost, rank-deficiency detection, and implementation flexibility.
1. Introduction.
- Fast, reliable QR remains a longstanding challenge: Householder and Givens methods are stable, but BLAS1/2 intensity and communication can limit performance on BLAS3-capable and distributed machines.Communication-avoiding algorithms are noted for asymptotically optimal communication cost.Source: §1 · p. 1
- The paper focuses on tall-and-skinny QR; existing TSQR improvements are described as unsatisfactory mainly because of implementation complexity.The target applications include randomized SVD, Krylov subspace methods, and LOBPCG.Source: §1 · p. 1
- CholeskyQR reduces communication and computation for tall-and-skinny matrices, but cond(A^T A) = cond(A)^2 can make it unstable, motivating preconditioning for ill-conditioned inputs.The introduction reviews CholeskyQR2, shifted CholeskyQR, and LU preconditioning as prior approaches.Source: §1 · p. 2
- The proposed randomized framework preconditions CholeskyQR and is presented as cheaper than CholeskyQR2-family preconditioners, able to detect rank deficiency with high probability, and easy to implement.If the system is rank deficient, the paper says only direct QR methods could work.Source: §1 · p. 2
2. CholeskyQR and its preconditioners.
This section reviews CholeskyQR’s efficiency and conditioning challenges, then develops a randomized XR preconditioning framework and outlines its sampling, parallel, and cost-analysis choices.
2.1. Existing methods review.
- CholeskyQR uses BLAS3 operations and simple reductions, but its sensitivity to conditioning can cause breakdown; repeated CholeskyQR2 improves stability but also has limits.CholeskyQR2 can break down when cond(A) = O(u^-1/2).Source: §2.1 · p. 3
2.2. XR-Based preconditioned CholeskyQR.
- The framework uses a rough QR factor R as a preconditioner, applies CholeskyQR to the transformed matrix, then recovers the final R factor.The rough factor comes from a sampled submatrix, whose LU or QR decomposition supplies an upper-triangular factor.Source: §2.2 · pp. 4–5
- When l is slightly larger than n, the partial XR factorization costs O(ln^2), approximately O(n^3), and its partial R factor is generally a suitable preconditioner.The framework requires the original matrix to have full rank and may break down if sampling makes R1 degenerate.Source: §2.2 · pp. 5–6
2.3. Strategies of choosing submatrix.
- Row extraction is easy to implement and communication-efficient, but can precondition poorly in rare extreme cases; Gaussian projection has optimal theoretical results but costly multiplication.The paper adopts row extraction for its section 4 tests and treats Gaussian projection as a theoretical supplement.Source: §2.3 · p. 6
2.4. Parallelism.
- In parallel, processors form local Gram matrices and reduce them to a root processor, which broadcasts R before each processor solves its triangular system..Source: §2.4 · p. 6
2.5. Complexity analysis.
- The complexity analysis compares the proposed algorithms with HouseholderQR, the CholeskyQR2 family, and TSQR, omitting lower-order terms..Source: §2.5 · p. 6, §2.5.1 · p. 7
2.5.1. Computational costs.
- The computational-cost table concerns computing Q only, excludes forming R by matrix multiplication, and omits lower-order terms.The supplied text gives the table’s scope but not its cell values.Source: §2.5.1 · p. 7, Table 1 · p. 7
2.5.2. Communication costs.
- Communication costs are compared by communication count and total communicated data; TSQR is omitted because the analysis considers collaborative communication..Source: §2.5.2 · p. 7, Table 2 · p. 7
3. Theoretical analysis.
The analysis uses concentration inequalities to estimate the conditioning of randomized row-submatrix preconditioners, with results for equal-probability sampling, unequal-probability sampling, and Gaussian sketches. It also identifies matrix structure as a boundary on the equal-probability result.
Analysis assumptions
- The analysis omits round-off error on the assumption that the small QR factorization and triangular solver are stable, with a separate analysis in Appendix A.Source: §3 · p. 7
Theorem 3.3 (Equal Probability Case)
- The equal-probability case gives a condition-number estimate for a submatrix formed by independently sampling rows uniformly from A.The estimate is stated for X defined in Algorithm 2.6; the supplied theorem passage does not include the bound itself.Source: §3 · p. 9
Equal-probability sampling limitation
- The equal-probability concentration result works when mθ(Q) is small; for Q = [I, 0], the required sample size is O(m log n log δ^-1), described as impractical as n grows.The paper attributes the difficulty to large θ(Q), which indicates that matrix entries concentrate in a lower-dimensional matrix.Source: §3 · pp. 10–11
Theorem 3.4 (Unequal Probability Case)
- Unequal-probability row sampling can sharpen the mθ(Q) dependence to n, the paper's stated optimal rate, though the strategy is described as impractical.The theorem samples row a_i scaled by ∥q_i∥^-1 with probability 1/(n∥q_i∥^2).Source: §3 · p. 10
Theorem 3.5 (Gaussian Ensemble Case)
- The Gaussian-ensemble analysis considers a sketch formed by left-multiplying A by an l × m matrix with independent standard-normal entries, for l > n.The paper presents this result as theoretical because Gaussian multiplication is computationally expensive; it notes a further estimate for l > 1.1n without the bound appearing in the supplied passage.Source: §3 · p. 11
4. Numerical results.
The experiments compare randomized LU- and QR-CholeskyQR with established QR methods across numerical stability, runtime, scalability, and sampling-rate tests. The proposed methods show stable accuracy, strong runtime performance among stable methods, and good scalability; increasing the sampling rate above 1 substantially reduces the preconditioned condition number.
4. Numerical results.
- The numerical study compares HouseholderQR, CholeskyQR, CholeskyQR2, shifted CholeskyQR3, and the two proposed randomized methods across accuracy, runtime, scalability, and sampling-rate experiments.The tests use C++ with OpenMPI, BLAS, and LAPACK libraries implemented in Intel MKL.Source: §4 · p. 12, §4.1 · p. 12
4.1. Setup.
- The experiments use double precision and generate test matrices from an SVD with ∥A∥₂ = 1 and cond(A) = κ = 1/σ.The setup also specifies computing configurations and uses l = 2n for the numerical-stability tests.Source: §4.1 · p. 12, Table 3 · p. 12, §4.2 · p. 12
4.2. Accuracy test.
- When κ ranges from 10^3 to 10^15, all methods except CholeskyQR maintain acceptable orthogonality; residuals are stable across methods, with slight differences favoring CholeskyQR over HouseholderQR.CholeskyQR’s orthogonality error is about O(κ^2u), and this behavior is reported only for κ ≤ 10^8.Source: §4.2 · p. 12, Figure 1 · p. 13, Figure 2 · p. 13
4.3. Runtime test.
- 24% and 82% more time: CholeskyQR2 and sCholeskyQR3, respectively, than rQR-CholeskyQR in the 32-process test; CholeskyQR2 collapses above κ = 10^8.In the single-process test, both proposed methods have the best runtime among stable methods and are faster than CholeskyQR2; runtime is proportional to matrix size m.Source: §4.3 · pp. 14–15, Figure 9 · p. 16, Figure 7 · p. 16
4.4. Scalability test.
- At 512 processes, methods run around 36 times faster than at 8 processes; under weak scaling, rQR-CholeskyQR takes 2.21 times longer as m grows from 10,000 to 5,120,000.The weak-scaling comparison fixes n, κ, and m/p; CholeskyQR2 and sCholeskyQR3 take 2.26 and 2.25 times longer, respectively.Source: §4.4 · p. 17, Table 4 · p. 17, Figure 10 · p. 17
4.5. Dependence on numbers of sampling rows.
- Increasing the sampling rate from 1 to 1.2 lowers the condition number of Q̂ from possibly 3000 to 20; the paper recommends rates from 1.5 to 2 for practical use.Further increases continue to lower the condition number, but less significantly.Source: §4.5 · p. 18, Figure 11 · p. 18
5. Applications.
Section 5 presents applications of the proposed methods to randomized SVD and least squares, while noting that its examples do not cover all possible applications.
5. Applications.
- The application discussion is explicitly incomplete: accelerating LOBPCG and block QR are identified as future-work directions.The authors note that tall-and-skinny QR takes substantial time in LOBPCG and that block QR relies heavily on tall-and-skinny matrices.Source: §5 · p. 18
5.1. Randomized singular value decomposition.
- In randomized SVD, the authors replace MATLAB’s built-in QR with rQR-CholeskyQR and report that acceleration grows as tested matrices become sparser.The experiments use sparse matrices from the SuiteSparse Matrix Collection and report per-iteration time; Table 6 compares QR and rQR-CholeskyQR.Source: §5.1 · p. 19, Table 6 · p. 20
5.2. Least square.
- The least-squares subsection notes that solving the normal equations requires full rank and remains vulnerable to ill-conditioned A^T A.It frames the section around the R factor of randomized QR; Table 6 is captioned as a QR versus rQR-CholeskyQR comparison.Source: §5.2 · p. 19, Table 6 · p. 20
Appendix A. Estimations on rQR-CholeskyQR under inexact procedure.
The appendix analyzes errors in an inexact rQR-CholeskyQR procedure, relating computed-factor accuracy to subroutine stability under stated condition-number assumptions.
Appendix A. Estimations on rQR-CholeskyQR under inexact procedure.
- The analysis assumes the QR and triangular-solver subroutines are forward stable in the ℓ2 norm.Under this stable-subroutine framing, the computed X is described as having a mild condition-number increase over X.Source: Appendix A · p. 20
- α-stability describes inexact QR, while β-stability bounds the error in approximating the triangular-system result AR−1.The appendix introduces these as separate stability notions for its error analysis.Source: Appendix A · p. 20
- If β cond(A) < 1/2 and α cond(A1) < 1/2, then ∥X − X̂∥2 is bounded by 2(β cond(A) + α cond(A1))∥X∥2.The proposition assumes an α-stable QR R factor for submatrix A1 and a β-stable triangular-system result.Source: Appendix A · p. 20
- For triangular systems, the stated backward-stability estimate gives ∥∆X∥F ≤ c m u cond(A)∥X∥F under mild assumptions.The appendix also recalls backward-stability bounds for Householder and Givens QR, with different stated dependence on dimensions.Source: Appendix A · p. 21