×

Linear-time CUR approximation of BEM matrices. (English) Zbl 1431.65022

Summary: In this paper we propose linear-time CUR approximation algorithms for admissible matrices obtained from the hierarchical form of Boundary Element matrices. We propose a new approach called geometric sampling to obtain indices of most significant rows and columns using information from the domains where the problem is posed. Our strategy is tailored to Boundary Element Methods (BEM) since it uses directly and explicitly the cluster tree containing information from the problem geometry. Our CUR algorithm has precision comparable with low-rank approximations created with the truncated QR factorization with column pivoting (QRCP) and the Adaptive Cross Approximation (ACA) with full pivoting, which are quadratic-cost methods. When compared to the well-known linear-time algorithm ACA with partial pivoting, we show that our algorithm improves, in general, the convergence error and overcomes some cases where ACA fails. We provide a general relative error bound for CUR approximations created with geometrical sampling. Finally, we evaluate the performance of our algorithms on traditional BEM problems defined over different geometries.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F25 Orthogonalization in numerical linear algebra
65F55 Numerical methods for low-rank matrix approximation; matrix compression
65N38 Boundary element methods for boundary value problems involving PDEs

Software:

hlib; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 2, 325-348 (1987) · Zbl 0629.65005
[2] Koumoutsakos, P., Fast Multipole Methods for Three-Dimensional N-body Problems, 377-390 (1995), Center for Turbulence Research, NASA Ames/Stanford Univ.
[3] Fong, W.; Darve, E., The black-box fast multipole method, J. Comput. Phys., 228, 8712-8725 (2009) · Zbl 1177.65009
[4] Martinsson, P. G.; Rokhlin, V., An accelerated kernel-independent fast multipole method in one dimension, SIAM J. Sci. Comput., 29, 3, 1160-1178 (2007) · Zbl 1154.65318
[5] Bebendorf, M., Hierarchical matrices, (Hierarchical Matrices (2008), Springer: Springer Leipzig, Germany)
[6] Börm, S., Efficient Numerical Methods for Non-local Operators: H-2 matrix Compression, Algorithms and Analysis (2010), European Mathematical Society · Zbl 1208.65037
[7] Hackbusch, W., Hierarchical matrices: algorithms and analysis, (Matrix Computations (2015), Springer Series in Computational Mathematics: Springer Series in Computational Mathematics Baltimore) · Zbl 1336.65041
[8] March, W.; Biros, G., Far-field compression for fast kernel summation methods in high dimensions, Appl. Comput. Harmon. Anal., 43, 1, 39-75 (2017) · Zbl 1365.65267
[9] Mahoney, M.; Drineas, P., CUR matrix decompositions for improved data analysis, Proc. Natl. Acad. Sci., 106, 3, 697-702 (2009) · Zbl 1202.68480
[10] Chiu, J.; Demanet, L., Sublinear randomized algorithms for skeleton decompositions, SIAM J. Matrix Anal. Appl., 34, 3, 1361-1383 (2013) · Zbl 1277.68296
[11] Ozdemir, N. A.; Lee, J.-F., A low-rank IE-QR algorithm for matrix compression in volume integral equations, IEEE Trans. Magn., 40, 2, 1017-1020 (2004)
[12] Kapur, S.; Long, D., N-body problems: IES3: Efficient electrostatic and electromagnetic simulation, IEEE Computat. Sci. Eng., 5, 4, 60-67 (1998)
[13] C. Boutsidis, M. Mahoney, P. Drineas, An improved approximation algorithm for the column subset selection problem, in: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 968-977. · Zbl 1420.68235
[14] Voronin, S.; Martinsson, P. G., Efficient algorithms for CUR and interpolative matrix decompositions, Adv. Comput. Math., 43, 3, 495-516 (2017) · Zbl 1369.65049
[15] Gu, M.; Eisenstat, S., Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Matrix Anal. Appl., 17, 4, 848-869 (1996) · Zbl 0858.65044
[16] Kumar, N.; G., S., Literature survey on low rank approximation of matrices, Linear Multilinear Algebra, 65, 11, 2212-2244 (2017) · Zbl 1387.65039
[17] Horn, R.; Johnson, C., Topics in matrix analysis, (Matrix Computations (1991), Cambridge University Press: Cambridge University Press New York, USA) · Zbl 0729.15001
[18] Mirsky, L., Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford Ser., 11, 2, 50-59 (1960) · Zbl 0105.01101
[19] Demmel, J.; Grigori, L.; Gu, M.; Xiang, H., Communication avoiding rank revealing QR factorization with column pivoting, SIAM J. Matrix Anal. Appl. (2015) · Zbl 1327.65078
[20] Pan, C.-T.; Tang, P., Bounds on singular values revealed by QR factorizations, BIT Numer. Math., 39, 4, 740-756 (1999) · Zbl 0944.65042
[21] Golub, G.; Van Loan, C., Matrix computations, (Matrix Computations (1996), Jonhs Hopkins University Press: Jonhs Hopkins University Press Baltimore) · Zbl 0865.65009
[22] Ayala, A.; Claeys, X.; Grigori, L., ALORA: Affine low-rank approximations, J. Sci. Comput., 79, 2, 1135-1160 (2019) · Zbl 1417.65120
[23] S. Goreinov, I. Oseledets, D. Savostyanov, E. Tyrtyshnikov, N. Zamarashkin, How to find a good submatrix, Research Report 08-10, ICM HKBU, Kowloon Tong, Hong Kong, 2008. · Zbl 1215.65078
[24] Goreinov, S.; Tyrtyshnikov, E., The maximal-volume concept in approximation by low-rank matrices, Contemp. Math., 280, 47-51 (2001) · Zbl 1003.15025
[25] Goreinov, S.; Tyrtyshnikov, E., Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm, Dokl. Math., 83, 3, 374-375 (2011) · Zbl 1252.65078
[26] Çivril, A.; Magdon-Ismail, M., Exponential inapproximability of selecting a maximum volume sub-matrix, Algorithmica, 65, 1, 159-176 (2013) · Zbl 1259.68086
[27] Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86, 4, 565-589 (2000) · Zbl 0966.65094
[28] Grigori, L.; Cayrols, S.; Demmel, J., Low rank approximation of a sparse matrix based on LU factorization with column and row tournament pivoting, SIAM J. Sci. Comput., 40, 2, C181-C209 (2018) · Zbl 1453.65090
[29] Higham, N., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics · Zbl 1011.65010
[30] Sommerville, D., An Introduction to the Geometry of n Dimensions (1958), Dover: Dover New York · Zbl 0086.35804
[31] Osinsky, A.; Zamarashkin, N., Pseudo-skeleton approximations with better accuracy estimates, Linear Algebra Appl., 537, 221-249 (2018) · Zbl 1376.65073
[32] Deshpande, A.; Rademacher, L.; Vempala, S.; Wang, G., Matrix approximation and projective clustering via volume sampling, Theory Comput., 2, 225-247 (2006) · Zbl 1213.68702
[33] Steinbach, O., Numerical approximation methods for elliptic boundary value problems: finite and boundary elements, (Numerical Approximation Methods for Elliptic Boundary Value Problems: Finite and Boundary Elements (2008), Springer: Springer New York, USA) · Zbl 1153.65302
[34] S. Rjasanow, Adaptive cross approximation of dense matrices, in: International Association for Boundary Element Methods Conference, IABEM, 2002.
[35] Demmel, J.; Grigori, L.; Hoemmen, M.; Langou, J., Communication-optimal parallel and sequential QR and LU factorizations (2008)
[36] Demmel, J.; Grigori, L.; Hoemmen, M.; Langou, J., Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comput., 34, 1, A206-A239 (2012) · Zbl 1241.65028
[37] Gray, A.; A., M., N-body problems in statistical learning, Adv. Neural Inf. Process. Syst., 521-527 (2001)
[38] S. Dasgupta, Y. Freund, Random projection trees and low dimensional manifolds, in: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC, 2008, pp. 537-546. · Zbl 1231.68114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.