# 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

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

• 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