10–11 Jun 2022
Dipartimento di Matematica, Università di Pisa
Europe/Rome timezone

Null space-based approaches for the least squares and symmetric saddle-point problems

10 Jun 2022, 15:30
30m
Aula Magna (Dipartimento di Matematica, Università di Pisa)

Aula Magna

Dipartimento di Matematica, Università di Pisa

L.go B. Pontecorvo, 5 56127 Pisa (PI) Italy

Speaker

Miroslav Tůma (Charles University)

Description

Consider saddle-point systems of the following form
A(uv)=(ABTB0)(uv)=(fg)(1) where ARn×n is large, sparse and symmetric positive definite and BRk×n(n>k) has full rank. Such systems arise in various scientific applications, including the finite element approximation of PDEs in which a constraint is enforced on a subset of unknowns via a global scalar Lagrange multiplier, numerical continuation methods for large nonlinear systems of equations, constrained optimization as well as in linear least squares problems [2]. Null-space methods represent one of possible solution approaches to solve such systems. Despite these solution approaches that compute a null-space ZRn×(nk) basis of the undetermined block B are traditional in various engineering communities and offer advantages in some situations, general techniques to obtain such bases useful for large and sparse A have not been studied frequently in the past. There are more reasons for this. One of them may be that the resulting transformed system with the matrix ZTAZ is often dense, or ill-conditioned, or both. Another reason may be that there is a lack of efficient preconditioners for the transformed systems even when the projected matrix ZTAZ is reasonably sparse. The core of the talk is devoted to discussing various algorithms to find the null-space basis Z. Although in several of the approaches treatment of B that does not have full-rank is not difficult, we do not treat such cases at length. Initial motivation for studying the null-space approaches in this talk is slightly different from the symmetric saddle-point problem given above. Consider the linear least-squares (LS) problem minxAxb2, where the system matrix ARm×n(mn) and the right-hand side bRm are given. Assume that a part of the rows of A is dense and the rows have been initially permuted such that the dense rows are the last rows of A. If we assume a conformal partitioning of the vector b we have A=(AsAd), AsRms×n, AdRmd×n, b=(bsbd), bsRms, bdRmd, where ms denotes the number of sparse rows of A, and md is the number of dense rows, with m=ms+md, msn>md1 and mdms. The normal equations that describe the solution [3] (not representing always the best way to get the solution) become Cx=(Cs+AdTAd)x=c, c=AsTbs+AdTbd,(2) where Cs=AsTAs is the reduced normal matrix. The solution of (2) can be obtained from the equivalent (n+md)×(n+md) system (CsAdTAdI)(xAdx)=(c0)(3) This is the system nearly of the form (1) with k=md,H=Cs,B=Ad. But the (2,2) block is nonzero and equal to the negative unit matrix of the appropriate dimension. Provided As has full column rank, Cs is symmetric positive definite. But the null-space based approach can be extended even if the (2,2) block is nonzero and Cs only positive semidefinite. This positive definiteness is quite common in the LS problems even when the whole A is of full column rank. The approach to solve (3) also in this case for the full rank LS problem (3) is motivated by the following simple lemma. \textbf{Lemma}: Consider A=AsAd, AsRms×n,AdRmd×n. If A is of full column rank, then Cs=AsTAs is positive definite on the null space of Ad. Success of any null-space approach then depends on constructing a suitable null-space basis that keeps the matrix ZTAZ sufficiently sparse and well-conditioned. Of course, it cannot be an orthogonal null-space basis computed, for example, by pivoted QR factorization of BT. We will discuss other approaches to find the null-space basis heavily based on the fact that B is wide. That is, it has far fewer rows than columns. The approaches include computing an oblique basis Z computed from more separate QR factorizations and an approach that adds rows of B one by one and extends the basis incrementally. Another approach for constructing Z is the right oblique conjugation. Applied to BRk×n it yields VRn×n and lower trapezoidal LRk×n satisfying BV=L.(4)The null-space basis is then formed by the last nk columns of V . This approach is directly related to Thesis of Michele Benzi [1]. Techniques implied by this Thesis have motivated the right oblique conjugation, and they may still offer further computational possibilities. Not only for constructing Z but possibly also for preconditioning of the linear systems with the matrix ZTAZ.

Our experimental results show that the null-space bases obtained from the mentioned approaches are of high quality and can push forward further research in optimization and solving constrained least squares. Linear least squares problems that contain a small number of dense rows arising from practical applications are used to illustrate our ideas and to explore their potential for solving large-scale systems. Our work was originally motivated by the paper by Howell [4]. A significant part of the obtained results has been published in [5].

References

[1] M. Benzi, A Direct Row-Projection Method For Sparse Linear Systems, Ph.D. Thesis, NCSU, 1993.
[2] M. Benzi, G.H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numerica,
14:1–137, 2005.
[3] ̊A. Bj ̈orck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996.
[4] J. S. Howell, Prestructuring sparse matrices with dense rows and columns via null space methods,
Numerical Linear Algebra with Applications, 25:1–30, 2018.
[5] J. A. Scott and M. T ̊uma, A null-space approach for large-scale symmetric saddle point systems with
a small and non zero (2,2) block, Numerical Algorithms, published online, 2022.

Presentation materials

There are no materials yet.