×

zbMATH — the first resource for mathematics

Fast factorization update for general elliptic equations under multiple coefficient updates. (English) Zbl 1442.65033

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Amestoy, I. Duff, J. L’Excellent, Y. Robert, F. Rouet and B. Uçar, On computing inverse entries of a sparse matrix in an out-of-core environment, SIAM J. Sci. Comput., 34 (2012), pp. 1975-1999. · Zbl 1252.05108
[2] J. M. Bennett, Triangular factors of modified matrices, Numer. Math., 7 (1965), pp. 217-221. · Zbl 0132.36204
[3] S. Chandrasekaran, M. Gu, and T. Pals, A fast \({ULV}\) decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 603-622. · Zbl 1120.65031
[4] S. M. Chan and V. Brandwajn, Partial matrix refactorization, IEEE Trans. Power Systems, 1 (1986), pp. 193-200.
[5] T. F. Chan and D. Goovaerts, Schur complement domain decomposition algorithms for spectral methods, Appl. Numer. Math., 6 (1989), pp. 53-64. · Zbl 0687.65106
[6] Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Trans. Math. Software, 35 (2008), 22.
[7] B. Cockburn, J. Gopalakrishnan, and R. Lazarov, Unified hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems, SIAM J. Numer. Anal., 47 (2007), pp. 1319-1365. · Zbl 1205.65312
[8] T. A. Davis, and W. W. Hager, Modifying a sparse Cholesky factorization, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606-627. · Zbl 0929.65012
[9] J. Djokić, Efficient Update of Hierarchical Matrices in the Case of Adaptive Discretization Schemes, Ph.D. thesis, Leipzig University, Leipzig, Germany, 2006. · Zbl 1113.65306
[10] J. Douglas and C. Huang, An accelerated domain decomposition procedure based on Robin transmission conditions, BIT, 37 (1997), pp. 678-686. · Zbl 0886.65114
[11] I. S. Duff and J. K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), pp. 302-325. · Zbl 0515.65022
[12] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345-363. · Zbl 0259.65087
[13] P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright, Maintaining LU factors of a general sparse matrix, Linear Algebra Appl., 88 (1987), pp. 239-270.ļearpage · Zbl 0618.65019
[14] A. Gillman and P. G. Martinsson, A direct solver with O(n) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method, SIAM J. Sci. Comput., 36 (2014), pp. A2023-A2046. · Zbl 1303.65099
[15] A. Gillman, A. H. Barnett, and P. G. Martinsson, A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, BIT, 55 (2015), pp. 141-170. · Zbl 1312.65201
[16] W. Hackbusch, L. Grasedyck, and S. Börm, An introduction to hierarchical matrices, Math. Bohem., 127 (2002), pp. 229-241. · Zbl 1007.65032
[17] W. Hackbusch and S. Börm, Data-sparse approximation by adaptive \(\mathcal{H}^2 \)-matrics, Computing, 69 (2002), pp. 1-35. · Zbl 1012.65023
[18] W. Hackbusch, B. N. Khoromskij, and R. Kriemann Direct Schur complement method by domain decomposition based on \(\mathcal{H} \)-matrix approximation, Comput. Vis. Sci., 8 (2005), pp. 179-188. · Zbl 1066.65143
[19] J. S. Hesthaven and T. Warburton, Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications, Springer, New York, 2007. · Zbl 1134.65068
[20] M. Jakobsen and B. Ursin, Full waveform inversion in the frequency domain using direct iterative T-matrix methods, J. Geophys. Eng., 12 (2015), pp. 400-418.
[21] R. Kittappa and R. E. Kleinman, Acoustic scattering by penetrable homogeneous objects, J. Math. Phys., 16 (1975), pp. 421-432. · Zbl 0306.76058
[22] R. Kress and G. F. Roach, Transmission problems for the Helmholtz equation, J. Math. Phys., 19 (1977), pp. 1433-1437. · Zbl 0433.35017
[23] L. Lin, C. Yang, J. C. Meza, J. Lu, and L. Ying, SelInv-An algorithm for selected inversion of a sparse symmetric matrix, ACM Trans. Math. Software, 37 (2011), 40. · Zbl 1365.65069
[24] X. Liu, J. Xia, and M. V. de Hoop, Parallel randomized and matrix-free direct solvers for large structured dense linear systems, SIAM J. Sci. Comput., 38 (2016), pp. S508-S538. · Zbl 1352.65094
[25] X. Liu, J. Xia, and M. V. de Hoop, A Fast Direct Elliptic Solver via Interconnected Hierarchical Structures, Purdue CCAM Report CCAM-2019-2, 2019.
[26] P. G. Martinsson, A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method, J. Comput. Phys., 242 (2013), pp. 460-479. · Zbl 1297.65169
[27] V. Minden, A. Damle, K. L. Ho, and L. Ying, A technique for updating hierarchical skeletonization-based factorizations of integral operators, Multiscale Model. Simul., 14 (2016), pp. 42-64. · Zbl 1329.65317
[28] MUMPS, A Multifrontal Massively Parallel Sparse Direct Solver, http://mumps.enseeiht.fr.
[29] PARDISO, Parallel Sparse Direct Solver PARDISO, http://www.pardiso-project.org.
[30] M. Pedneault, C. Turc, and Y. Boubendir, Schur complement domain decomposition methods for the solution of multiple scattering problems, IMA J. Appl. Math., 82 (2017), pp. 1104-1134.
[31] F. H. Rouet, Memory and Performance Issues in Parallel Multifrontal Factorizations and Triangular Solutions with Sparse Right-Hand Sides, Ph.D. thesis, University of Toulouse, Toulouse, France, 2012.
[32] O. Schenk, and K. Gärtner Solving unsymmetric sparse systems of linear equations with PARDISO, Future Gener. Comput. Syst., 20 (2004), pp. 475-487. · Zbl 1062.65035
[33] B. Willemsen, A. Malcolm, and W. Lewis, A numerically exact local solver applied to salt boundary inversion in seismic full-waveform inversion, Geophys. J. Int., 204 (2016), pp. 1703-1720.
[34] J. Xia, Randomized sparse direct solvers, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 197-227. · Zbl 1269.65029
[35] J. Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. A832-A860. · Zbl 1266.15022
[36] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1382-1411. · Zbl 1195.65031
[37] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976. · Zbl 1240.65087
[38] Z. Xin, J. Xia, M. V. de Hoop, S. Cauley, and V. Balakrishnan, A distributed-memory randomized structured multifrontal method for sparse direct solutions, SIAM J. Sci. Comput., 39 (2017), pp. C292-C318. · Zbl 1393.65002
[39] E. L. Yip, A note on the stability of solving a rank-\(p\) modification of a linear system by the Sherman-Morrison-Woodbury formula, SIAM J. Sci. Stat. Comput., 7 (1984), pp. 507-513. · Zbl 0628.65020
[40] Y. Zhang and A. Gillman, A fast direct solver for boundary value problems on locally perturbed geometries, J. Comput. Phys., 356 (2018), pp. 356-371. · Zbl 1380.65451
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.