Advancing matrix computations with randomized preprocessing

DOI10.1007/978-3-642-13182-0_28zbMATH Open1284.65061arXiv1210.7476OpenAlexW1562588540MaRDI QIDQ3569755FDOQ3569755

Authors: Victor Y. Pan, Guoliang Qian, Ai-Long Zheng 

Publication date: 22 June 2010

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1210.7476

Recommendations

• Matrix computations and polynomial root-finding with preprocessing
• Additive preconditioning for matrix computations
• scientific article; zbMATH DE number 2086387
• Solving linear systems of equations with randomization, augmentation and aggregation
• Randomized preprocessing of homogeneous linear systems of equations

Mathematics Subject Classification ID

Randomized algorithms (68W20) Ill-posedness and regularization problems in numerical linear algebra (65F22) Numerical computation of matrix norms, conditioning, scaling (65F35)

Cited In (9)

• Additive Preconditioning for Matrix Computations
• New studies of randomized augmentation and additive preprocessing
• Solving linear systems of equations with randomization, augmentation and aggregation
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Matrix computations and polynomial root-finding with preprocessing
• Additive preconditioning for matrix computations
• Randomized preconditioning of the MBA algorithm
• Randomized circulant and Gaussian pre-processing
• Using randomization to make recursive matrix algorithms practical

This page was built for publication: Advancing matrix computations with randomized preprocessing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569755)