Ubaru, Shashanka; Saad, Yousef Sampling and multilevel coarsening algorithms for fast matrix approximations. (English) Zbl 1463.65096 Numer. Linear Algebra Appl. 26, No. 3, e2234, 22 p. (2019). The paper discusses approximation of large and sparse matrices and proposes a new approach based primarily on coarsening techniques. The authors consider several standard applications of the new strategy, in particular, computation of the partial singular value decomposition, column subset selection problem and graph sparsification. Furthermore, other interesting applications where one faces large and sparse matrices are mentioned. Approximation quality of the coarsening strategy based on column matching is theoretically analyzed. The achieved error bounds are similar to those developed earlier for randomized sampling. Performance of the coarsening techniques is demonstrated in various considered applications also numerically. The paper shows that the coarsening techniques can often provide similar results as other and more expensive alternatives. Reviewer: Miroslav Tůma (Praha) Cited in 1 Document MSC: 65F55 Numerical methods for low-rank matrix approximation; matrix compression 65F50 Computational methods for sparse matrices 68W25 Approximation algorithms Keywords:graph coarsening; hypergraph coarsening; fast matrix approximation; multilevel methods; randomization; latent semantic indexing; subspace iteration; SVD approximation Software:ORL face; Matlab; SuiteSparse PDFBibTeX XMLCite \textit{S. Ubaru} and \textit{Y. Saad}, Numer. Linear Algebra Appl. 26, No. 3, e2234, 22 p. (2019; Zbl 1463.65096) Full Text: DOI arXiv