PinT preconditioner for forward-backward evolutionary equations. (English) Zbl 1530.65114
Summary: Solving the linear system \((\mathcal{KK}^\top)^{-1}\boldsymbol{b}\) is often the major computational burden when a forward-backward evolutionary equation must be solved in a problem, where \(\mathcal{K}\) is the so-called all-at-once matrix of the forward subproblem after space-time discretization. An efficient solver requires a good preconditioner for \(\mathcal{KK}^\top\). Inspired by the structure of \(\mathcal{K}\), we precondition \(\mathcal{KK}^\top\) by \(\mathcal{P}_\alpha\mathcal{P}_\alpha^\top\) with \(\mathcal{P}_\alpha\) being a block \(\alpha\)-circulant matrix constructed by replacing the Toeplitz matrices in \(\mathcal{K}\) by the \(\alpha\)-circulant matrices. By a block Fourier diagonalization of \(\mathcal{P}_\alpha\), the computation of the preconditioning step \((\mathcal{P}_\alpha\mathcal{P}_\alpha^\top)^{-1}\boldsymbol{r}\) is parallelizable for all the time steps. We give a spectral analysis for the preconditioned matrix \((\mathcal{P}_\alpha\mathcal{P}_\alpha^\top)^{-1}(\mathcal{KK}^\top)\) and prove that for any one-step stable time-integrator the eigenvalues of \((\mathcal{P}_\alpha\mathcal{P}_\alpha^\top)^{-1}(\mathcal{KK}^\top)\) spread in a mesh-independent interval \([(1+\sqrt{2}\delta)^{-1},(1-\sqrt{2}\delta)^{-1}]\) if the parameter \(\alpha\) weakly scales in terms of the number of time steps \(N_t\) as \(\alpha=\delta/\sqrt{N_t}\), where \(\delta\in(0,1/\sqrt{2})\) is a free constant. Two applications of the proposed preconditioner are illustrated: PDE-constrained optimal control problems and parabolic source identification problems. Numerical results for both problems indicate that spectral analysis predicts the convergence rate of the preconditioned conjugate gradient method very well.
MSC:
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65J20 | Numerical solutions of ill-posed problems in abstract spaces; regularization |
| 65H10 | Numerical computation of solutions to systems of equations |
| 49M41 | PDE constrained optimization (numerical aspects) |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 65L06 | Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations |
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 65M15 | Error bounds for initial value and initial-boundary value problems involving PDEs |
| 65Y05 | Parallel numerical computation |
| 15B05 | Toeplitz, Cauchy, and related matrices |
| 93B05 | Controllability |
| 93B20 | Minimal systems representations |
Keywords:
forward-backward equations; parallel-in-time (PinT); all-at-once system; preconditioner; optimal control problems; parabolic source identification; spectral analysisReferences:
| [1] | Andrle, M. and El Badia, A., On an inverse source problem for the heat equation. Application to a pollution detection problem, II, Inverse Probl. Sci. Eng., 23 (2015), pp. 389-412. · Zbl 1326.65121 |
| [2] | Andrle, M. and Duong, T. H., On an inverse source problem for the heat equation. Application to a pollution detection problem, J. Inverse Ill-Posed Probl., 10 (2002), pp. 585-599. · Zbl 1028.35164 |
| [3] | Brown, L. C. and Barnwell, T. O., The Enhanced Stream Water Quality Models QUAL2E and QUAL2E-UNCAS: Documentation and User Manual, U.S. Environmental Protection Agency, Athens, GA, 1987. |
| [4] | Banjai, L. and Peterseim, D., Parallel multistep methods for linear evolution problems, IMA J. Numer. Anal., 32 (2012), pp. 1217-1240. · Zbl 1248.65100 |
| [5] | Barker, A. T., Rees, T., and Stoll, M., A fast solver for an \(\mathcal{H}_1\) regularized PDE-constrained optimization problem, Commun. Comput. Phys., 19 (2016), pp. 143-167. · Zbl 1373.49028 |
| [6] | Biegler, L. T., Ghattas, O., Heinkenschloss, M., Keyes, D., and van Bloemen Waanders, B., Real-Time PDE-Constrained Optimization, SIAM, Philadelphia, PA, 2007. · Zbl 1117.49004 |
| [7] | Bini, D., Latouche, G., and Meini, B., Numerical Methods for Structured Markov Chains, Oxford University Press, New York, 2005. · Zbl 1076.60002 |
| [8] | Borzì, A. and Kunisch, K., A Multigrid Method for Optimal Control of Time-Dependent Reaction Diffusion Processes, Fast Solution of Discretized Optimization Problems, , Birkhäuser, Basel, 2001. · Zbl 0990.49020 |
| [9] | Borzì, A. and Schulz, V., Computational Optimization of Systems Governed by Partial Differential Equations, SIAM, Philadelphia, PA, 2012. · Zbl 1240.90001 |
| [10] | Braess, D. and Peisker, P., On the numerical solution of the biharmonic equation and the role of squaring matrices for preconditioning, IMA J. Numer. Anal., 6 (1986), pp. 393-404. · Zbl 0616.65108 |
| [11] | Danieli, F. and Wathen, A. J., All-at-once solution of linear wave equations, Numer. Linear Algebra Appl., 28 (2021), e2386. · Zbl 07478618 |
| [12] | Danieli, F., Southworth, B., and Wathen, A. J., Space-time block preconditioning for incompressible flow, SIAM J. Sci. Comput., 44 (2022), pp. A337-A363. · Zbl 1482.65042 |
| [13] | Farcas, A. and Lesnic, D., The boundary-element method for the determination of a heat source dependent on one variable, J. Engrg. Math., 54 (2006), pp. 375-388. · Zbl 1146.80007 |
| [14] | Goddard, A. and Wathen, A., A note on parallel preconditioning for all-at-once evolutionary PDEs, Electron. Trans. Numer. Anal., 51 (2019), pp. 135-150. · Zbl 1422.65232 |
| [15] | Gander, M. J. and Wu, S. L., Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization technique, Numer. Math., 143 (2019), pp. 489-527. · Zbl 1472.65083 |
| [16] | Golub, G. and Van Loan, C., Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 2012. · Zbl 0559.65011 |
| [17] | Graham, I., Spence, E., and Vainikko, E., Domain decomposition preconditioning for high frequency Helmholtz problems with absorption, Math. Comp., 86 (2017), pp. 2089-2127. · Zbl 1368.65250 |
| [18] | Hasano \(\check{\text{g}}\) lu, A. H. and Romanov, V. G., Introduction to Inverse Problems for Differential Equations, 2nd ed., Springer, Berlin, 2017. · Zbl 1385.65053 |
| [19] | Hairer, E. and Wanner, G., Solving Ordinary Differential Equations II: Stiff and Differential-algebraic Problems, Springer, Berlin, 2000. · Zbl 0729.65051 |
| [20] | Herzog, R., Pearson, J. W., and Stoll, M., Fast iterative solvers for an optimal transport problem, Adv. Comput. Math., 45 (2019), pp. 495-517. · Zbl 1415.65070 |
| [21] | Hinze, M., Pinnau, R., Ulbrich, M., and Ulbrich, S., Optimization with PDE constraints, in Mathematical Modelling: Theory and Applications, Springer, Berlin, 2009. · Zbl 1167.49001 |
| [22] | Hirshman, S. P., Perumalla, K. S., Lynch, V. E., and Sanchez, R., BCYCLIC: A parallel block tridiagonal matrix cyclic solver, J. Comput. Phys., 229 (2010), pp. 6392-6404. · Zbl 1197.65032 |
| [23] | Hocking, R. and Greif, C., Optimal complex relaxation parameters in multigrid for complex-shifted linear systems, SIAM J. Matrix Anal. Appl., 42 (2021), pp. 475-502. · Zbl 1468.65218 |
| [24] | Kunisch, K. and Zou, J., Iterative choices of regularization parameters in linear inverse problems, Inverse Problems, 14 (1998), pp. 1247-1264. · Zbl 0917.65053 |
| [25] | Lin, X.-L. and Ng, M., An all-at-once preconditioner for evolutionary partial differential equations, SIAM J. Sci. Comput., 43 (2021), pp. A2766-A2784. · Zbl 07379636 |
| [26] | Lin, X., Ng, M., and Sun, H., Efficient preconditioner of one-sided space fractional diffusion equation, BIT Numer. Math., 58 (2018), pp. 729-748. · Zbl 1404.65136 |
| [27] | Lin, X. L. and Zhang, Z., A Parallel-in-Time Preconditioner for the Schur Complement of Parabolic Optimal Control Problems, preprint, arXiv:2109.12524 [math.NA], 2021. |
| [28] | Leveque, S. and Pearson, J. W., Fast iterative solver for the optimal control of time-dependent PDEs with Crank-Nicolson discretization in time, Numer. Linear Algebra Appl., 29 (2022), e2419. · Zbl 07511600 |
| [29] | Lions, J.-L., Optimal Control of Systems Governed by Partial Differential Equations, Springer, Berlin, 1971. · Zbl 0203.09001 |
| [30] | Liu, J. and Wu, S. L., A fast block \(\alpha \)-circulant preconditioner for all-at-once systems from wave equations, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 1912-1943. · Zbl 1460.65102 |
| [31] | Liu, J. and Pearson, J. W., Parameter-robust preconditioning for the optimal control of the wave equation, Numer. Algorithms, 83 (2019), pp. 1171-1203. · Zbl 07171737 |
| [32] | Morozov, V. A., Methods for Solving Incorrectly Posed Problems, Springer, Berlin, 1984. · Zbl 0549.65031 |
| [33] | McDonald, E., Pestana, J., and Wathen, A., Preconditioning and iterative solution of all-at-once systems for evolutionary partial differential equations, SIAM J. Sci. Comput., 40 (2018), pp. A1012-A1033. · Zbl 1392.65036 |
| [34] | Ma, Y. J., Fu, C., and Zhang, Y. X., Identification of an unknown source depending on both time and space variables by a variational method, Appl. Math. Model., 36 (2012), pp. 5080-5090. · Zbl 1252.65106 |
| [35] | Nili Ahmadabadi, M., Arab, M., and Maalek Ghaini, F. M., The method of fundamental solutions for the inverse space-dependent heat source problem, Eng. Anal. Bound. Elem., 33 (2009), pp. 1231-1235. · Zbl 1180.80054 |
| [36] | Pearson, J. W. and Wathen, A. J., A new approximation of the Schur complement in preconditioners for PDE constrained optimization, Numer. Linear Algebra Appl., 19 (2012), pp. 816-829. · Zbl 1274.65187 |
| [37] | Pearson, J. W., Stoll, M., and Wathen, A. J., Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1126-1152. · Zbl 1263.65035 |
| [38] | Pearson, J. W., Fast iterative solvers for large matrix systems arising from time-dependent Stokes control problems, Appl. Numer. Math., 108 (2016), pp. 87-101. · Zbl 1346.65035 |
| [39] | Reevet, D. E. and Spivack, M., Determination of a source term in the linear diffusion equation, Inverse Problems, 10 (1994), pp. 1335-3344. · Zbl 0811.35165 |
| [40] | Saitoh, S., Tuan, V., and Yamamoto, M., Reverse convolution inequalities and applications to inverse heat source problems, J. Inequal. Pure Appl. Math., 3 (2003), 80. · Zbl 1029.44002 |
| [41] | Savateev, E. G., On problems of determining the source function in a parabolic equation, J. Inverse Ill-Posed Probl., 3 (1995), pp. 83-102. · Zbl 0828.35142 |
| [42] | Stoll, M., One-shot solution of a time-dependent time-periodic PDE-constrained optimization problem, IMA J. Numer. Anal., 34 (2014), pp. 1554-1577. · Zbl 1303.65050 |
| [43] | Stoll, M. and Wathen, A., All-at-once solution of time-dependent Stokes control, J. Comput. Phys., 232 (2013), pp. 498-515. |
| [44] | Wathen, A., Some comments on preconditioning for normal equations and least squares, SIAM Rev., 64 (2022), pp. 640-649. · Zbl 1507.65070 |
| [45] | Wu, S. L. and Zhou, T., Parallel implementation for the two-stage SDIRK methods via diagonalization, J. Comput. Phys., 428 (2021), 110076. · Zbl 07511430 |
| [46] | Wu, S.-L., Zhang, H., and Zhou, T., Solving time-periodic fractional diffusion equations via diagonalization technique and multigrid, Numer. Linear Algebra Appl., 25 (2018), e2178. · Zbl 1513.65347 |
| [47] | Wu, S.-L., Zhou, T., and Zhou, Z., A uniform spectral analysis for preconditioned all-at-once system from first-order and second-order evolutionary problems, SIAM J. Matrix Anal. Appl., 43 (2022), pp. 1331-1353. · Zbl 1496.65152 |
| [48] | Wu, S. N. and Zhou, Z., A parallel-in-time algorithm for high-order BDF methods for diffusion and subdiffusion equations, SIAM J. Sci. Comput., 43 (2021), pp. A3627-A3656. · Zbl 1491.65084 |
| [49] | Xie, J. and Zou, J., An improved model function method for choosing regularization parameters in linear inverse problems, Inverse Problems, 18 (2002), pp. 631-643. · Zbl 1012.65050 |
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.
