Abstract
Abstract Optimization problems with constraints in the form
of a partial differential equation arise frequently in the process
of engineering design. The discretization of PDE-constrained
optimization problems results in large-scale linear systems
of saddle-point type. In this paper we propose and develop a novel
approach to solving such systems by exploiting so-called quasiseparable
matrices. One may think of a usual quasiseparable matrix as of a discrete
analog of the Green's function of a one-dimensional differential operator.
Nice feature of such matrices is that almost every algorithm which
employs them has linear complexity. We extend the application
of quasiseparable matrices to problems in higher dimensions.
Namely, we construct a class of preconditioners which can be computed
and applied at a linear computational cost.
Their use with appropriate Krylov methods leads to algorithms
of nearly linear complexity.
Key words: Saddle-point problems, PDE-constrained optimization, Preconditioning, Optimal control, Linear systems, Quasiseparable matrices.