×
Durastante, Fabio; Furci, Isabella

Spectral analysis of saddle-point matrices from optimization problems with elliptic PDE constraints. (English) Zbl 1466.62395

Electron. J. Linear Algebra 36, 773-798 (2020).
Summary: The main focus of this paper is the characterization and exploitation of the asymptotic spectrum of the saddle-point matrix sequences arising from the discretization of optimization problems constrained by elliptic partial differential equations. They uncover the existence of an hidden structure in these matrix sequences, namely, they show that these are indeed an example of Generalized Locally Toeplitz (GLT) sequences. They show that this enables a sharper characterization of the spectral properties of such sequences than the one that is available by using only the fact that they deal with saddle-point matrices. Finally, they exploit it to propose an optimal preconditioner strategy for the GMRES, and Flexible-GMRES methods.

Cited in 2 Documents

MSC:

62M15 Inference from stochastic processes and spectral analysis
65F08 Preconditioners for iterative methods
15B05 Toeplitz, Cauchy, and related matrices

Keywords:

saddle-point matrices; optimal control; GLT (Generalized Locally Toeplitz) theory; preconditioning

Software:

FEniCS; FFC
Cite Review PDF
Full Text: arXiv Link

References:

[1] M.S. Alnæs, J. Blechta, J. Hake, A. Johansson, B. Kehlet, A. Logg, C. Richardson, J. Ring, M.E. Rognes, and G.N. Wells. The FEniCS Project Version 1.5, Archive of Numerical Software, 3, 2015. Available athttps://doi.org/10.11588/ans. 2015.100.20553,http://nbn-resolving.de/urn:nbn:de:bsz:16-ans-205530.
[2] O. Axelsson, S. Farouq, and M. Neytcheva; Comparison of preconditioned Krylov subspace iteration methods for PDEconstrained optimization problems: Poisson and convection-diffusion control.Numer. Algorithms, 73:631-663, 2016. Available athttps://doi.org/10.1007/s11075-016-0111-1. · Zbl 1353.65059
[3] O. Axelsson and M. Neytcheva. Eigenvalue estimates for preconditioned saddle point matrices.Numer. Linear Algebra Appl., 13:339-360, 2006. Available athttps://doi.org/10.1002/nla.469. · Zbl 1224.65080
[4] Z.-Z. Bai. Block preconditioners for elliptic PDE-constrained optimization problems.Computing, 91:379-395, 2011. Available athttps://doi.org/10.1007/s00607-010-0125-9. · Zbl 1242.65121
[5] M. Benzi, G.H. Golub, and J. Liesen. Numerical solution of saddle point problems.Acta Numer., 14:1-137, 2005. Available athttps://doi.org/10.1017/S0962492904000212. · Zbl 1115.65034
[6] M. Benzi and V. Simoncini. On the eigenvalues of a class of saddle point matrices.Numer. Math., 103:173-196, 2006. Available athttps://doi.org/10.1007/s00211-006-0679-9. · Zbl 1103.65033
[7] L. Bergamaschi. On eigenvalue distribution of constraint-preconditioned symmetric saddle point matrices.Numer. Linear Algebra Appl., 19:754-772, 2012. Available athttps://doi.org/10.1002/nla.806. · Zbl 1274.65084
[8] D. Bertaccini and F. Durastante.Iterative Methods and Preconditioning for Large and Sparse Linear Systems with Applications. Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2018. · Zbl 1386.65001
[9] D. Braess.Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, third edition (translated from the German by Larry L. Schumaker). Cambridge University Press, Cambridge, 2007. Available athttps://doi.org/10. 1017/CBO9780511618635. · Zbl 1118.65117
[10] S. Cipolla and F. Durastante. Fractional PDE constrained optimization: An optimize-then-discretize approach with LBFGS and approximate inverse preconditioning.Appl. Numer. Math., 123:43-57, 2018. Available athttps://doi.org/ 10.1016/j.apnum.2017.09.001. · Zbl 1377.65070
[11] M. Donatelli, A. Dorostkar, M. Mazza, M. Neytcheva, and S. Serra-Capizzano. Function-based block multigrid strategy for a two-dimensional linear elasticity-type problem.Comput. Math. Appl., 74:1015-1028, 2017. Available athttps: //doi.org/10.1016/j.camwa.2017.05.024. · Zbl 1390.74176
[12] F. Durastante and S. Cipolla. Fractional PDE constrained optimization: box and sparse constrained problems. In:Numerical Methods for Optimal Control Problems, Springer International Publishing, Cham, Chapter 6, 111-135, 2018. Available athttps://doi.org/10.1007/978-3-030-01959-4 6. · Zbl 1416.49033
[13] S.-E. Ekstr¨om, I. Furci, and S. Serra-Capizzano. Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices.BIT, 58:937-968, 2018. Available athttps://doi.org/10.1007/s10543-018-0715-z. · Zbl 1405.65051
[14] S.-E. Ekstr¨om, C. Garoni, and S. Serra-Capizzano. Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?Exp. Math., 27:478-487, 2018. Available athttps://doi.org/10.1080/10586458.2017.1320241. · Zbl 1405.15037
[15] C. Garoni, M. Mazza, and S. Serra-Capizzano. Block generalized locally toeplitz sequences: From the theory to the applications.Axioms, 7, 2018. Available athttps://doi.org/10.3390/axioms7030049. · Zbl 1434.65034
[16] C. Garoni and S. Serra-Capizzano.Generalized Locally Toeplitz Sequences: Theory and Applications, Vol. I. Springer, Cham, 2017. Available athttps://doi.org/10.1007/978-3-319-53679-8. · Zbl 1376.15002
[17] C. Garoni and S. Serra-Capizzano.Generalized Locally Toeplitz Sequences: Theory and Applications, Vol. II. Springer, Cham, 2018. Available athttps://doi.org/10.1007/978-3-030-02233-4. · Zbl 1448.47004
[18] N.I.M. Gould and V. Simoncini. Spectral analysis of saddle point matrices with indefinite leading blocks.SIAM J. Matrix Anal. Appl., 31:1152-1171, 2009. Available athttps://doi.org/10.1137/080733413. · Zbl 1200.15007
[19] U. Grenander and G. Szeg˝o.Toeplitz Forms and Their Applications, second edition. Chelsea Publishing Co., New York, 1984. · Zbl 0611.47018
[20] Y.-F. Ke and C.-F. Ma. Some preconditioners for elliptic PDE-constrained optimization problems.Comput. Math. Appl., 75:2795-2813, 2018. Available athttps://doi.org/10.1016/j.camwa.2018.01.009. · Zbl 1415.65248
[21] A. Logg, B.K. Ølgaard, M.E. Rognes, and G.N. Wells. FFC: The FEniCS Form Compiler. In: A. Logg, K.-A. Mardal, and G.N. Wells (editors),Automated Solution of Differential Equations by the Finite Element Method, Lecture Notes in Computational Science and Engineering, Vol. 84, Chapter 11, Springer, 2012. · Zbl 1247.65105
[22] M.F. Murphy, G.H. Golub, and A.J. Wathen. A note on preconditioning for indefinite linear systems.SIAM J. Sci. Comput., 21:1969-1972, 2000. Available athttps://doi.org/10.1137/S1064827599355153,https://doi.org/10.1137/ S1064827599355153. · Zbl 0959.65063
[23] I. Perugia and V. Simoncini. Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations.Numer. Linear Algebra Appl., (Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Minneapolis, MN, 1999) 7:585-616, 2000. Available athttps://doi.org/10.1002/1099-1506(200010/12)7: 7/8h585::AID-NLA214i3.3.CO;2-6. · Zbl 1051.65038
[24] J. Pestana and A.J. Wathen. The antitriangular factorization of saddle point matrices.SIAM J. Matrix Anal. Appl., 35:339-353, 2014. Available athttps://doi.org/10.1137/130934933. · Zbl 1385.65027
[25] T. Rees and M. Stoll. Block-triangular preconditioners for PDE-constrained optimization.Numer. Linear Algebra Appl., 17:977-996, 2010. Available athttps://doi.org/10.1002/nla.693. · Zbl 1240.65097
[26] T. Rusten and R. Winther. A preconditioned iterative method for saddlepoint problems.SIAM J. Matrix Anal. Appl., (Iterative Methods in Numerical Linear Algebra, Copper Mountain, CO, 1990) 13:887-904, 1992. · Zbl 0760.65033
[27] S. Serra-Capizzano. Asymptotic results on the spectra of block Toeplitz preconditioned matrices.SIAM J. Matrix Anal. Appl., 20:31-44, 1999. Available athttps://doi.org/10.1137/S0895479896310160. · Zbl 0932.65037
[28] S. Serra-Capizzano. Generalized locally Toeplitz sequences: Spectral analysis and applications to discretized partial differential equations.Linear Algebra Appl., (Special issue on Structured Matrices: Analysis, Algorithms and Applications, Cortona, 2000) 366:371-402, 2003. Available athttps://doi.org/10.1016/S0024-3795(02)00504-9. · Zbl 1028.65109
[29] S. Serra-Capizzano. The GLT class as a generalized Fourier analysis and applications.Linear Algebra Appl., 419:180-233, 2006. Available athttps://doi.org/10.1016/j.laa.2006.04.012. · Zbl 1109.65032
[30] S. Serra-Capizzano, D. Bertaccini, and G.H. Golub. How to deduce a proper eigenvalue cluster from a proper singular value cluster in the nonnormal case.SIAM J. Matrix Anal. Appl., 27:82-86, 2005. Available athttps://doi.org/10. 1137/040608027. · Zbl 1088.65031
[31] D. Sesana and V. Simoncini. Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices. Linear Algebra Appl., 438:2683-2700, 2013. Available athttps://doi.org/10.1016/j.laa.2012.11.022. · Zbl 1263.65029
[32] P. Tilli A note on the spectral distribution of Toeplitz matrices.Linear Multilinear Algebra, 45:147-159, 1998. Available athttps://doi.org/10.1080/03081089808818584. · Zbl 0951.65033
[33] F. Tr¨oltzsch.Optimal Control of Partial Differential Equations: Theory, Methods and Applications(translated from the 2005 German original by J¨urgen Sprekels). Graduate Studies in Mathematics, Vol. 112, American Mathematical Society, Providence, RI, 2010. Available athttps://doi.org/10.1090/gsm/112 · Zbl 1195.49001
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.