Exploiting Structure in Matrix Computations is Sometimes Necessary but Always Desirable

Natasa Strabic (University of Manchester)

G.205 Alan Turing Building,

The wonderful world of matrices is rich in structure, ranging from simple and obvious
element patterns to special properties, all of which can be exploited to develop faster and
more accurate algorithms with lower computational cost and memory requirements than
general methods, as well as to compute more physically meaningful solutions. Arguably,
one of the most desirable structures a matrix can possess is positive (semi)de finiteness
and in this talk we present two applications where it plays a major role.


The first is focused on the Bartels-Stewart method to solve stable, non-negative defi -
nite Lyapunov equations \(A^*X + XA = -C\), for which the solution \(X\) should be positive
semidefi nite. However, for some problems in practice it happens that the computed so-
lution is in fact indefi nite. To overcome this, the general method is modi ed to compute
the Cholesky factor \(R\) of the solution directly, thus guaranteeing positive semidefi niteness
via \(X = R^TR\).


In the second part of the talk we describe shrinking, a new approach to replacing a
real indefi nite matrix with a positive semidefi nite one, while the leading positive defi nite
block of the matrix remains fi xed and all the unfi xed elements are minimally perturbed.
The problems of this type appear in many financial and data analysis applications. We
show how the problem can be solved by the bisection method and posed as a generalized
eigenvalue problem, and we demonstrate how exploiting positive defi niteness in these two
methods leads to impressive computational savings.

References:

[1] S. J. Hammarling. Numerical Solution of the Stable, Non-negative De finite Lya-
punov Equation. IMA J. Numer. Anal., 2:303-323, 1982
[2] S. J. Hammarling. Numerical Solution of the Discrete-time, Convergent, Non-
negative Defi nite Lyapunov Equation. Systems and Control Letters, 17:137-139, 1991
[3] N. J. Higham, N. Strabic and V. Sego. Restoring De finiteness via Shrinking, with
an Application to Correlation Matrices with a Fixed Block. MIMS EPrint 2014.54

Import this event to your Outlook calendar
▲ Up to the top