Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights

The nonsymmetric Lanczos algorithm reduces a general matrix to tridiagonal by generating two sequences of vectors which satisfy a mutual bi-orthogonality property. The process can proceed as long as the two vectors generated at each stage are not mutually orthogonal, otherwise the process breaks down. In this paper, we propose a variant that does not break down by grouping the vectors into clusters and enforcing the bi-orthogonality property only between different clusters, but relaxing the property within clusters. We show how this variant of the matrix Lanczos algorithm applies directly to a problem of computing a set of orthogonal polynomials and associated indefinite weights with respect to an indefinite inner product, given the associated moments. We discuss the close relationship between the modified Lanczos algorithm and the modified Chebyshev algorithm. We further show the connection between this last problem and checksum-based error correction schemes for fault-tolerant computing.