4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Why would one want to do that? $\endgroup$ – Wolfgang Bangerth May 14 '16 at 11:55
  • $\begingroup$ 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. $\endgroup$ – gpavanb May 14 '16 at 17:18
  • $\begingroup$ 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? $\endgroup$ – gpavanb May 14 '16 at 18:20
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gpavanb May 15 '16 at 23:04
  • $\begingroup$ @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. $\endgroup$ – Carl Christian May 16 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.