An alternative method for SPP with full rank (2,1)-block matrix and nonzero right-hand side vector

We propose an alternative method to solve large linear saddle point problems arising from computational sciences and engineering such as finite element approximations to Stokes problems, image reconstructions, tomography, genetics, statistics, and model order reductions for dynamical systems. Such problems have large sparse 2-by-2 block structure coefficient matrices with zero (2,2)-block matrix. A new technique is presented to solve saddle point problems with full row rank (2,1)-block matrix and nonzero right-hand side vector. By constructing a projection matrix and transforming the original problem into a least squares problem, a new reduced least squares problem is solved via the well-known iterative method LSMR. Numerical experiments show that this new method works very well for the specified saddle point systems.

PDF

___

[1] Arrow KJ, Hurwicz L, Uzawa H. Studies in Linear and Nonlinear Programming. Stanford University Press, Palo Alto, 1958.
[2] Axelsson O. Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations. Linear Algebra and its Applications 1980; 29: 1-16. doi: 10.1016/0024-3795(80)90226-8
[3] Axler S. Linear Algebra Done Right. Springer, New York, 1997.
[4] Bai ZZ, Golub GH, Ng MK. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems for non-hermitian positive definite linear systems. SIAM Journal on Matrix Analysis and Applications 2003; 24 (3): 603-626. doi: 10.1137/S0895479801395458
[5] Fong DC, Saunders M. LSMR: An iterative algorithm for sparse least-squares problems. SIAM Journal on Scientific Computing 2010; 33 (5): 2950-2971. doi: 10.1137/10079687X
[6] Golub GH, Kahan W. Calculating the singular values and pseudo-inverse of a matrix. Journal of Society for Industrial and Applied Mathematics: Series B, Numerical Analysis 1965; 2 (2): 205-224.
[7] Kuhn HW, Tucker AW. Nonlinear programming. Proceedings of the 2nd Berkeley Symposium on Mathematics, Statistics and Probability, University of California Press, Berkeley, 1951; 481-492.
[8] Paige CC, Saunders MA. Solution of Sparse Indefinite Systems of Linear Equations. SIAM Journal on Numerical Analysis 1975; 12 (4): 617-629. doi: 10.1137/0712047
[9] Perugia I, Simoncini V, Arioli M. Linear Algebra Methods in a Mixed Approximation of Magnetostatic Problems. SIAM Journal on Scientific Computing 1999; 21 (3): 1085-1101. doi: 10.1137/S1064827598333211
[10] Pestana J, Rees T. Null-Space Preconditioners for Saddle Point Systems. SIAM Journal on Matrix Analysis and Applications 2016; 37 (3): 1103-1128. doi: 10.1137/15M1021349
[11] Reid N. Saddlepoint Methods and Statistical Inference. Statistical Science 1988; 3 (2): 213-227. doi: 10.1214/ss/1177012906
[12] Saad Y. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2003. doi: 10.1137/1.9780898718003
[13] Saad Y, Schultz MH. GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing 1986; 7 (3): 856-869. doi: 10.1137/0907058
[14] Tuma M. A Note on the LDLT Decomposition of Matrices from Saddle-Point Problems. SIAM Journal on Matrix Analysis and Applications 2002; 23 (4): 903-915. doi: 10.1137/S0895479897321088
[15] Turek S. Efficient Solvers for Incompressible Flow Problems - An Algorithmic and Computational Approach. Springer, Berlin, Heidelberg, 1999. doi: 10.1007/978-3-642-58393-3
[16] Watkins DS. Fundamentals of Matrix Computations. Wiley Interscience, New York, 2002.