>> help band_Lanczos Band Lanczos method This implementation is essentially Algorithm 5.1 in Roland W. Freund, Model reduction methods based on Krylov subspaces, Acta Numerica, 12 (2003), pp. 267-319. ----------------------------------------------------------------------------- Notes: 1) The matrices A, R, and L are allowed to be complex. 2) The biorthogonalizations performed in the algorithm are with respect to the bilinear form (w,v) = w^T v (= w.' * v), where w^T (= w.') denotes the transpose of w. 3) This algorithm explicitly enforces only the minimum possible amount of biorthogonalization. Moreover, only the entries below (and for T on) the diagonal of the Lanczos matrices T and Tt are computed directly via inner products and norms of candidate vectors and previously deflated vectors; the other entries are obtained via the relation D * T = Tt.' * D between T and the transpose Tt.' of Tt. 4) This algorithm has no built-in look-ahead procedure to continue in the case of a breakdown or near-breakdown, and instead, the algorithm simply stops in this case. ----------------------------------------------------------------------------- Usage: result = band_Lanczos(A,R,L,nmax) result = band_Lanczos(A,R,L,nmax,sflag) result = band_Lanczos(A,R,L,nmax,sflag,tol) result = band_Lanczos(A,R,L,nmax,sflag,tol,n,result) where A is a matrix, or, result = band_Lanczos(@(x,tfl) afun(x,tfl,...),R,L,nmax) result = band_Lanczos(@(x,tfl) afun(x,tfl,...),R,L,nmax,sflag) result = band_Lanczos(@(x,tfl) afun(x,tfl,...),R,L,nmax,sflag,tol) result = band_Lanczos(@(x,tfl) afun(x,tfl,...),R,L,nmax,sflag, ... tol,n,result) where "afun" is a function such that y = afun(x,0,...) computes the matrix-vector product y = A x (= A * x) with A and y = afun(x,1,...) computes the matrix-vector product y = A^T x (= A.' * x) with the transpose A^T of A ----------------------------------------------------------------------------- Required inputs: A = a square matrix or an (anonymous) function that computes matrix-vector products with A and A^T R = matrix the m columns of which are the right starting vectors L = matrix the p columns of which are the left starting vectors nmax = maximum number of pairs of right and left Lanczos vectors to be generated It is assumed that A is a square matrix and that A, R, and L have the same number of rows; these assumptions are checked when the input A is a matrix, but not when A is a function. ----------------------------------------------------------------------------- Optional inputs: sflag = an integer that controls the storage of the right and left Lanczos vectors: sflag = 0 means that only the vectors needed for the biorthogonalization are stored; a nonzero value of sflag means that all vectors are stored tol = a structure that contains tolerances and parameters for the deflation procedure and the breakdown check n = a nonnegative integer; n > 0 means that a previous call to the function "band_Lanczos" has generated n pairs of right and left Lanczos vectors and that the current call to "band_Lanczos" resumes the iteration at step n+1; n = 0 means that the band Lanczos method is started from scratch result = the output structure of the previous call to "band_Lanczos" if n > 0; if n = 0, this input is ignored If sflag is not provided as an input, sflag = 0 is used. If "tol" is provided as an input, it needs to contain tol.defl_tol = unscaled deflation tolerance tol.brk_tol = tolerance for breakdown check and values of the following two flags: tol.defl_flag = 0 (use unscaled deflation tolerance) 1 (use scaled deflation tolerance) 2 (use scaled deflation tolerance only for the starting blocks R and L) 3 (use scaled deflation tolerance except for the starting blocks R and L) tol.normA_flag = 1 (an estimate for the norm of A is generated within the algorithm) 2 (an estimate for the norm of A is provided as tol.normA) If tol.normA_flag = 2, then an estimate for the norm of A needs to be provided as tol.normA If "tol" is not provided as an input, the following default values are used: tol.defl_tol = sqrt(eps) (eps = machine precision) tol.brk_tol = 100 * eps; tol.defl_flag = 1 tol.normA_flag = 1 If n is not provided as an input, n = 0 is used and the optional input "result" is ignored. a If n > 0, the input "result" needs to be provided. It is assumed, but not checked, that "result" is the output structure of a previous call to the function "band_Lanczos" (applied to the same matrices A, R, and L). In this case, the inputs "sflag" and "tol" are ignored and tol = result.tol and sflag = result.sflag are used instead. ----------------------------------------------------------------------------- On return, "result" is a structure the fields of which include the following quantities: result.n = number of pairs of right and left Lanczos vectors that were generated result.V = matrix V the columns of which are the stored right Lanczos vectors; if sflag = 0, V has at most p+1 columns and these columns are the right Lanczos vectors that are needed for biorthogonalization; if sflag is nonzero, V contains the first n right Lanczos vectors result.W = matrix W the columns of which are the stored left Lanczos vectors; if sflag = 0, W has at most m+1 columns and these columns are the left Lanczos vectors that are needed for biorthogonalization; if sflag is nonzero, W contains the first n left Lanczos vectors result.Vh_defl = matrix Vh_defl the columns of which are the candidate vectors for the next mc right Lanczos vectors and the m-mc deflated right vectors result.Wh_defl = matrix Wh_defl the columns of which are the candidate vectors for the next pc left Lanczos vectors and the p-pc deflated left vectors result.D = vector D the entries of which are the products (W(:,k)).' * V(:,k), k = 1, 2, ..., n result.T = the n x n matrix T that represents the oblique projection of the matrix A onto the subspace spanned by the columns of V, and orthogonally to the subspace spanned by the columns of W; A, V, W, and T are connected via the relation W.' * A * V = (W.' * V) * T result.Tt = the n x n matrix Tt that represents the oblique projection of the matrix A.' onto the subspace spanned by the columns the columns of W, and orthogonally to the subspace spanned by the columns of V; A, V, W, and Tt are connected via the relation V.' * A.' * W = (V.' * W) * Tt result.rho = the matrix rho that contains the coefficients used to turn the right starting vectors (in R) into the first right Lanczos vectors; R, V, W, and rho are connected via the relation W.' * R = W.' * V * rho result.eta = the matrix eta that contains the coefficients used to turn the left starting vectors (in L) into the first left Lanczos vectors; L, V, W, and eta are connected via the relation V.' * L = V.' * W * eta ----------------------------------------------------------------------------- This routine can be run in incremental fashion. Example 1: result = band_Lanczos(A,R,L,nmax0,sflag,tol) n = result.n result = band_Lanczos(A,R,L,nmax,sflag,tol,n,result) The first call to the function "band_Lanczos" runs the band Lanczos method from scratch and generates n pairs of right and left Lanczos vectors. The second call to the function of "band_Lanczos" resumes the iteration at step n+1. Example 2 (Band Lanczos method, run one step at a time): result = band_Lanczos(A,R,L,1,sflag,tol,0,[]) for n = 1 : nmax - 1, result = band_Lanczos(A,R,L,n+1,[],[],result.n,result) end This will run the band Lanczos method for nmax steps. ----------------------------------------------------------------------------- BANDITS: a Matlab Package of Band Krylov Subspace Iterations Copyright (c) 2018-2019 Roland W. Freund See LICENSE.txt for license -----------------------------------------------------------------------------