A matching Schur complement preconditioning technique for inverse source problems. (English) Zbl 07859312
Summary: Numerical discretization of a regularized inverse source problem leads to a non-symmetric saddle point linear system. Interestingly, the Schur complement of the non-symmetric saddle point system is Hermitian positive definite (HPD). Then, we propose a preconditioner matching the Schur complement (MSC). Theoretically, we show that the preconditioned conjugate gradient (PCG) method for a linear system with the preconditioned Schur complement as coefficient has a linear convergence rate independent of the matrix size and value of the regularization parameter involved in the inverse problem. Fast implementations are proposed for the matrix-vector multiplication of the preconditioned Schur complement so that the PCG solver requires only quasi-linear operations. To the best of our knowledge, this is the first solver with guarantee of linear convergence for the inversion of Schur complement arising from the discrete inverse problem. Combining the PCG solver for inversion of the Schur complement and the fast solvers for the forward problem in the literature, the discrete inverse problem (the saddle point system) is solved within a quasi-linear complexity. Numerical results are reported to show the performance of the proposed matching Schur complement (MSC) preconditioning technique.
MSC:
| 65Mxx | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
| 65Fxx | Numerical linear algebra |
| 35Kxx | Parabolic equations and parabolic systems |
Keywords:
preconditioning technique for Schur complement; inverse space-dependent source problem; saddle point system; size-independent convergence of iterative solverReferences:
| [1] | Ament, Marco; Knittel, Gunter; Weiskopf, Daniel; Strasser, Wolfgang, A parallel preconditioned conjugate gradient solver for the Poisson problem on a multi-gpu platform, (2010 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2010, IEEE), 583-592 |
| [2] | Axelsson, Owe; Lindskog, Gunhild, On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48, 5, 499-523, 1986 · Zbl 0564.65017 |
| [3] | Benzi, Michele; Olshanskii, Maxim A., Field-of-values convergence analysis of augmented Lagrangian preconditioners for the linearized Navier-Stokes problem, SIAM J. Numer. Anal., 49, 2, 770-788, 2011 · Zbl 1245.76044 |
| [4] | Benzi, Michele; Golub, Gene H.; Liesen, Jörg, Numerical solution of saddle point problems, Acta Numer., 14, 1-137, 2005 · Zbl 1115.65034 |
| [5] | Bini, Dario A.; Meini, Beatrice, The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond: in memoriam of Gene H. Golub, Numer. Algorithms, 51, 23-60, 2009 · Zbl 1170.65021 |
| [6] | Cannon, John Rozier; DuChateau, Paul, Structural identification of an unknown source term in a heat equation, Inverse Probl., 14, 3, 535, 1998 · Zbl 0917.35156 |
| [7] | Dodson, David S.; Levin, Stewart A., A tricyclic tridiagonal equation solver, SIAM J. Matrix Anal. Appl., 13, 4, 1246-1254, 1992 · Zbl 0760.65023 |
| [8] | Dou, Fang-Fang; Fu, Chu-Li; Yang, Feng-Lian, Optimal error bound and Fourier regularization for identifying an unknown source in the heat equation, J. Comput. Appl. Math., 230, 2, 728-737, 2009 · Zbl 1219.65100 |
| [9] | Elman, H. C.; Silvester, D. J.; Wathen, A. J., Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, Numer. Math. Sci., 2014 · Zbl 1304.76002 |
| [10] | Fatullayev, Afet Golayoglu, Numerical solution of the inverse problem of determining an unknown source term in a heat equation, Math. Comput. Simul., 58, 3, 247-253, 2002 · Zbl 0994.65100 |
| [11] | Fatullayev, Afet Golayoglu, Numerical solution of the inverse problem of determining an unknown source term in a two-dimensional heat equation, Appl. Math. Comput., 152, 3, 659-666, 2004 · Zbl 1077.65107 |
| [12] | Fulton, Scott R.; Ciesielski, Paul E.; Schubert, Wayne H., Multigrid methods for elliptic problems: a review, Mon. Weather Rev., 114, 5, 943-959, 1986 |
| [13] | Golub, Gene H.; Van Loan, Charles F., Matrix Computations, 2013, JHU Press · Zbl 1268.65037 |
| [14] | Jiang, Yi; Liu, Jun; Wang, Xiang-Sheng, A direct parallel-in-time quasi-boundary value method for inverse space-dependent source problems, J. Comput. Appl. Math., Article 114958 pp., 2022 · Zbl 1505.65254 |
| [15] | Ke, Rihuan; Ng, Michael K.; Wei, Ting, Efficient preconditioning for time fractional diffusion inverse source problems, SIAM J. Matrix Anal. Appl., 41, 4, 1857-1888, 2020 · Zbl 1464.65031 |
| [16] | Lin, Xue-lei; Ng, Michael, An all-at-once preconditioner for evolutionary partial differential equations, SIAM J. Sci. Comput., 43, 4, A2766-A2784, 2021 · Zbl 07379636 |
| [17] | Maday, Yvon; Turinici, Gabriel, The parareal in time iterative solver: a further direction to parallel implementation, (Domain Decomposition Methods in Science and Engineering, 2005, Springer), 441-448 · Zbl 1067.65102 |
| [18] | Murphy, Malcolm F.; Golub, Gene H.; Wathen, Andrew J., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 6, 1969-1972, 2000 · Zbl 0959.65063 |
| [19] | Valero-Lara, Pedro; Pinelli, Alfredo; Prieto-Matias, Manuel, Fast finite difference Poisson solvers on heterogeneous architectures, Comput. Phys. Commun., 185, 4, 1265-1272, 2014 · Zbl 1344.65103 |
| [20] | Wathen, Andrew J., Preconditioning, Acta Numer., 24, 329-376, 2015 · Zbl 1316.65039 |
| [21] | Yang, Fan; Fu, Chu-Li, A simplified Tikhonov regularization method for determining the heat source, Appl. Math. Model., 34, 11, 3286-3299, 2010 · Zbl 1201.65177 |
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.
