×

Iterative solution of Saddle-point systems from radial basis function (RBF) interpolation. (English) Zbl 1420.65023

Summary: Scattered data interpolation using conditionally positive definite radial basis functions typically leads to large, dense, and indefinite systems of saddle-point type. Due to ill-conditioning, the iterative solution of these systems requires an effective preconditioner. Using the technique of \(\mathcal{H}\)-matrices, we propose, analyze, and compare two preconditioning approaches: transformation of the indefinite into a positive definite system using either Lagrangian augmentation or the nullspace method combined with subsequent \(\mathcal{H}\)-Cholesky preconditioning. Numerical tests support the theoretical condition number estimates and illustrate the performance of the proposed preconditioners which are suitable for problems with up to \(N \approx 40000\) centers in two or three spatial dimensions.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65D05 Numerical interpolation
41A05 Interpolation in approximation theory

Software:

PetRBF; H2Lib; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. K. Beatson, W. A. Light, and S. Billings, Fast solution of the radial basis function interpolation equations: Domain decomposition methods, SIAM J. Sci. Comput., 22 (2001), pp. 1717-1740, https://doi.org/10.1137/S1064827599361771. · Zbl 0982.65015
[2] M. Bebendorf and W. Hackbusch, Stabilized rounded addition of hierarchical matrices, Numer. Linear Algebra Appl., 14 (2007), pp. 407-423. · Zbl 1199.65135
[3] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1-137, https://doi.org/10.1017/S0962492904000212. · Zbl 1115.65034
[4] M. Benzi and M. A. Olshanskii, An augmented Lagrangian-based approach to the Oseen problem, SIAM J. Sci. Comput., 28 (2006), pp. 2095-2113, https://doi.org/10.1137/050646421. · Zbl 1126.76028
[5] S. Börm, H2LIB Software Library, University of Kiel, Kiel, Germany, http://www.h2lib.org, 2017.
[6] S. Börm and S. Le Borne, \( \mathcal{H} \)-LU factorization in preconditioners for augmented Lagrangian and grad-div stabilized saddle point systems, Internat. J. Numer. Methods Fluids, 68 (2012), pp. 83-98, https://doi.org/10.1002/fld.2495. · Zbl 1426.76224
[7] S. Le Borne, Block computation and representation of a sparse nullspace basis of a rectangular matrix, Linear Algebra Appl., 428 (2008), pp. 2455-2467, https://doi.org/10.1016/j.laa.2007.11.025. · Zbl 1142.65041
[8] S. Le Borne and M. Wende, Domain decomposition methods in scattered data interpolation with conditionally positive definite radial basis functions, Comput. Math. Appl. 77 (2019), pp. 1178-1196, https://doi.org/10.1016/j.camwa.2018.10.042. · Zbl 1442.65405
[9] S. Boyd and L. Vanderberghe, Convex Optimization, 7th printing with corrections, Cambridge University Press, Cambridge, UK, 2009.
[10] F. Cheng, On conditioning of saddle-point matrices with Lagrangian augmentation, Appl. Math. Comput., 248 (2014), pp. 4-7. · Zbl 1338.65072
[11] J. Cherrie, R. Beatson, and G. Newsam, Fast evaluation of radial basis functions: Methods for generalized multiquadrics in \(\mathbb R^n\), SIAM J. Sci. Comput., 23 (2002), pp. 1549-1571, https://doi.org/10.1137/S1064827500367609. · Zbl 1009.65007
[12] M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Stud. Math. Appl. 15, North-Holland, Amsterdam, 1983. · Zbl 0525.65045
[13] G. H. Golub and C. Greif, On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 24 (2003), pp. 2076-2092, https://doi.org/10.1137/S1064827500375096. · Zbl 1036.65033
[14] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer Ser. Comput. Math. 49, Springer, Heidelberg, 2015, https://ebookcentral.proquest.com/lib/gbv/detail.action?docID=4213051. · Zbl 1336.65041
[15] W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, 2nd ed., Springer, Cham, 2016, https://doi.org/10.1007/978-3-319-28483-5. · Zbl 1347.65063
[16] J. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2 (1960), pp. 84-90, https://doi.org/10.1007/BF01386213. · Zbl 0090.34505
[17] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 2002, https://doi.org/10.1137/1.9780898718027. · Zbl 1011.65010
[18] N. J. Higham, A survey of condition number estimation for triangular matrices, SIAM Rev., 29 (1987), pp. 575-596, https://doi.org/10.1137/1029112. · Zbl 0635.65049
[19] A. Iske, S. Le Borne, and M. Wende, Hierarchical matrix approximation for kernel-based scattered data interpolation, SIAM J. Sci. Comput., 39 (2017), pp. A2287-A2316, https://doi.org/10.1137/16M1101167. · Zbl 1375.65012
[20] Q. T. Le Gia, I. H. Sloan, and A. J. Wathen, Stability and preconditioning for a hybrid approximation on the sphere, Numer. Math., 118 (2011), pp. 695-711, https://doi.org/10.1007/s00211-011-0369-0. · Zbl 1223.65022
[21] N. Mastronardi and P. Van Dooren, The antitriangular factorization of symmetric matrices, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 173-196, https://doi.org/10.1137/110858860. · Zbl 1272.65031
[22] J. Pestana and A. J. Wathen, The antitriangular factorization of saddle point matrices, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 339-353, https://doi.org/10.1137/130934933. · Zbl 1385.65027
[23] M. Powell, Some algorithms for thin plate spline interpolation to functions of two variables, in Proceedings of the Conference on Advances in Computational Mathematics, World Scientific, River Edge, NJ, 1994, pp. 303-319. · Zbl 0839.65004
[24] T. Rees and J. Scott, A comparative study of null-space factorizations for sparse symmetric saddle point systems, Numer. Linear Algebra Appl., 25 (2018), e2103, https://doi.org/10.1002/nla.2103. · Zbl 1424.65060
[25] G. Roussos and B. J. Baxter, Rapid evaluation of radial basis functions, J. Comput. Appl. Math., 180 (2005), pp. 51-70, https://doi.org/10.1016/j.cam.2004.10.002. · Zbl 1069.65008
[26] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718003. · Zbl 1031.65046
[27] H. Wendland, Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math. 17, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1185.65022
[28] R. Yokota, L. A. Barba, and M. G. Knepley, PetRBF–a parallel \(\mathcal{O}({N})\) algorithm for radial basis function interpolation with Gaussians, Comput. Methods Appl. Mech. Engrg., 199 (2010), pp. 1793-1804. · Zbl 1231.65026
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.