Solve for $C$ such that $C^{T}AC$ is banded of given width

Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$ can be rectangular.

• Why would one want to do that? – Wolfgang Bangerth May 14 '16 at 11:55
• I feel there is an automated way to generate a change of basis such that we get a banded inner-product matrix to solve for PDE discretization problems. $A$ corresponds to the inner product using standard basis functions and $C^{T}AC$ corresponds to the transformed basis. – gpavanb May 14 '16 at 17:18
• I'm also interested if this problem is referred to using a standard name. Since $C$ can be rectangular and hence not necessarily orthogonal, this is not exactly preconditioning. But is this viewed as a "generalized" Lanczos algorithm? – gpavanb May 14 '16 at 18:20

1 Answer

Yes. The block Lanczos algorithm

http://www.netlib.org/utk/people/JackDongarra/etemplates/node250.html

produces a block triangular matrix where you control the block size, hence the bandwidth.

Certainly, one can argue that a block tridiagonal matrix is not a "proper" banded matrix as there regular patches of certain zeros within the band.

If you want a proper banded matrix then you should do a two-sided reduction to upper quasi upper Hessenberg form with $r>1$ subdiagonals using, say, Householder reflections, see

http://www.sciencedirect.com/science/article/pii/S0167819111000482

If this article is not freely available to you, then much of the same information is freely available here

http://www8.cs.umu.se/research/uminf/reports/2010/014/part1.pdf

This is an approach which is distinctly different from the Lanczos algorithms

In both cases the decision to seek out a form which is not mathematically optimal stems from a realization that it is no longer the raw flop count which determines the run time. Reducing memory operations, communication and the need synchronization is frequently much more important.

A term which is relevant to your problem is "symmetric band reduction".

• Is there an accessible numerical implementation of the proper banded matrix version? I'm currently using dsyrdb from the MKL library which uses Bischof2000 and results in a block triangular matrix. – gpavanb May 15 '16 at 23:04
• @gpavanb You should write the primary author Lars Karlsson, see www8.cs.umu.se/~larsk and ask. I am sure that he will be delighted to receive a request. I can not imagine that he has not released the code. – Carl Christian May 16 '16 at 17:35