A random matrix is likely to be well conditioned, and motivated by this well known property we employ random matrix multipliers to advance some fundamental matrix computations. This includes numerical stabilization of Gaussian elimination with no pivoting as well as block Gaussian elimination, approximation of the leading and trailing singular spaces of an ill conditioned matrix, associated with its largest and smallest singular values, respectively, and approximation of this matrix by low-rank matrices, with further extensions to computing numerical ranks and the approximation of tensor decomposition. We formally support the efficiency of the proposed techniques where we employ Gaussian random multipliers, but our extensive tests have consistently produced the same outcome where instead we used sparse and structured random multipliers, defined by much fewer random parameters compared to the number of their entries.
Preconditioning of linear systems of equations is a classical subject @cite_42 , @cite_18 , @cite_11 . Randomized multiplicative preconditioning for numerical stabilization of GENP was proposed in [Section 12.2] PGMQ and @cite_35 , but with no formal support for this approach. On low-rank approximation we refer the reader to the survey @cite_39 . We cite these and other related works throughout the paper and refer to [Section 11] PQZb on further bibliography. For a natural extension of our present work, one can combine randomized matrix multiplication with randomized augmentation and additive preprocessing of @cite_0 , @cite_7 , @cite_12 , @cite_1 , @cite_25 , @cite_36 , @cite_46 .
@cite_35 @cite_18 @cite_7 @cite_36 @cite_42 @cite_1 @cite_39 @cite_0 @cite_46 @cite_25 @cite_12 @cite_11
1981220107 1506588095 2117756735 2017951318 1560263223
This article surveys preconditioning techniques for the iterative solution of large linear systems, with a focus on algebraic methods suitable for general sparse matrices. Covered topics include progress in incomplete factorization methods, sparse approximate inverses, reorderings, parallelization issues, and block and multilevel extensions. Some of the challenges ahead are also discussed. An extensive bibliography completes the paper. Random matrices tend to be well conditioned, and we employ this well known property to advance matrix computations. We prove that our algorithms employing Gaussian random matrices are efficient, but in our tests the algorithms have consistently remained as powerful where we used sparse and structured random matrices, defined by much fewer random parameters. We numerically stabilize Gaussian elimination with no pivoting as well as block Gaussian elimination, precondition an ill conditioned linear system of equations, compute numerical rank of a matrix without orthogonalization and pivoting, approximate the singular spaces of an ill conditioned matrix associated with its largest and smallest singular values, and approximate this matrix with low-rank matrices, with applications to its 2-by-2 block triangulation and to tensor decomposition. Some of our results and techniques can be of independent interest, e.g., our estimates for the condition numbers of random Toeplitz and circulant matrices and our variations of the Sherman--Morrison--Woodbury formula. Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed—either explicitly or implicitly—to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the @math dominant components of the singular value decomposition of an @math matrix. (i) For a dense input matrix, randomized algorithms require @math floating-point operations (flops) in contrast to @math for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to @math passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data. Abstract Our randomized preprocessing enables pivoting-free and orthogonalization-free solution of homogeneous linear systems of equations. In the case of Toeplitz inputs, we decrease the estimated solution time from quadratic to nearly linear, and our tests show dramatic decrease of the CPU time as well. We prove numerical stability of our approach and extend it to solving nonsingular linear systems, inversion and generalized (Moore–Penrose) inversion of general and structured matrices by means of Newton’s iteration, approximation of a matrix by a nearby matrix that has a smaller rank or a smaller displacement rank, matrix eigen-solving, and root-finding for polynomial and secular equations and for polynomial systems of equations. Some by-products and extensions of our study can be of independent technical intersest, e.g., our extensions of the Sherman–Morrison–Woodbury formula for matrix inversion, our estimates for the condition number of randomized matrix products, and preprocessing via augmentation. List of Algorithms Preface 1. Introduction. Brief Overview of the State of the Art Notation Review of Relevant Linear Algebra Part I. Krylov Subspace Approximations. 2. Some Iteration Methods. Simple Iteration Orthomin(1) and Steepest Descent Orthomin(2) and CG Orthodir, MINRES, and GMRES Derivation of MINRES and CG from the Lanczos Algorithm 3. Error Bounds for CG, MINRES, and GMRES. Hermitian Problems-CG and MINRES Non-Hermitian Problems-GMRES 4. Effects of Finite Precision Arithmetic. Some Numerical Examples The Lanczos Algorithm A Hypothetical MINRES CG Implementation A Matrix Completion Problem Orthogonal Polynomials 5. BiCG and Related Methods. The Two-Sided Lanczos Algorithm The Biconjugate Gradient Algorithm The Quasi-Minimal Residual Algorithm Relation Between BiCG and QMR The Conjugate Gradient Squared Algorithm The BiCGSTAB Algorithm Which Method Should I Use? 6. Is There A Short Recurrence for a Near-Optimal Approximation? The Faber and Manteuffel Result Implications 7. Miscellaneous Issues. Symmetrizing the Problem Error Estimation and Stopping Criteria Attainable Accuracy Multiple Right-Hand Sides and Block Methods Computer Implementation Part II. Preconditioners. 8. Overview and Preconditioned Algorithms. 9. Two Example Problems. The Diffusion Equation The Transport Equation 10. Comparison of Preconditioners. Jacobi, Gauss--Seidel, SOR The Perron--Frobenius Theorem Comparison of Regular Splittings Regular Splittings Used with the CG Algorithm Optimal Diagonal and Block Diagonal Preconditioners 11. Incomplete Decompositions. Incomplete Cholesky Decomposition Modified Incomplete Cholesky Decomposition 12. Multigrid and Domain Decomposition Methods. Multigrid Methods Basic Ideas of Domain Decomposition Methods.