## 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.

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.

Original language | English |
---|---|

Publisher | ArXiv |

Publication status | Published - 2011 |