Matlab codes ------------- Codes_shar -- A shar file containing all of the codes listed below driveP.m -- Demonstrates behavior of power method Drives pow_inf and pow_rq pow_inf.m -- Simple power method demo routine uses max element for eigenvalue estimate normalizes to the unit ball in infinity norm pow_rq.m -- Simple power method demo routine uses Rayleigh Quotient for eigenvalue estimate normalizes to the unit ball in 2- norm krylov.m -- Demonstrates effect of roundoff in obvious implementation for getting orthogonal basis for Krylov space Arnoldi.m -- The simple Arnoldi process ArnoldiC.m -- The Arnoldi process with DGKS correction for orthogonality driveA.m -- Driver for Arnoldi. Sets up A, calls Arnoldi, displays residuals driveA2.m -- Driver for Arnoldi. Assumes A and v_1 exist. calls Arnoldi, displays residuals. Use after first call to driveA, demonstrate effect of increasing k. Repeat k = k+10; driveA2 several times driveAC.m -- Driver for ArnoldiC. Assumes A and v_1 exist. calls ArnoldiC, displays residuals. Use after first call to driveA, demonstrate effect of increasing k. Repeat k = k+10; driveAC several times orthdemo.m -- Demonstrates loss of orthogonality in simple Arnoldi and how the DGKS correction remedies the problem in ArnlodiC eigconv.m -- Demonstrates convergence pattern of Ritz values to Eigenvalues as the size k of the Arnoldi factorization increases ritzest.m -- Displays Ritz estimates and exact differences for eigenvalues | \lambda - \theta| and norms of residuals norm(Ax - x \theta) as k increases polyR.m -- Demonstrates polynomial restart action on a vector with respect to a symmetric positive definite matrix A. Displays Chebyshev filter polynomial T constructed to damp unwanted coefficients and then displays how expansion coefficients decay as v <- T(A)v is done over and over eigenui.m -- A gui driver to look at convergence of Arnoldi and Lanczos Toggles for nonsymmetric, symmetric, and symmetric "waterfall" drives eigen_update.m This is a fancy version of eigconv.m eigen_update.m -- Implements the gui toggles for eigenui Lanczos.m -- The Lanczos process using just the 3-term recurrence with NO orthogonalization of the Lanczos vectors. driveL.m -- Sets up a symmetric random matrix and does 10 steps of Lanczos driveL2.m -- Continue after executing driveL Repeat k = k+10; driveL2 several times Displays lowest few and largest few eigenvalues, Ritz-values, and differences. Illustrates convergence pattern to the extreme eigenvalues and also the loss of orthogonality in the Lanczos vectors as convergence takes place. Eventually, it will demonstrate the introduction of "ghost" eigenvalues (or spurious eigenvalues) For the given example, k ~ 100 will probably show ghost eigenvalues. Sym_ritz.m -- Graphical illustration of how eigenvalues of successive tridiagonal T_k's interlace and why convergence to the extreme eigenvalues happens first. Lanconv_gui.m -- Gui interface to graphical illustration of how eigenvalues of successive tridiagonal T_k's interlace and why convergence to the extreme eigenvalues happens first. Lanconv_update.m -- Implements the gui toggles for Lanconv_gui driveQR.m -- Drives qriter.m driveQRS.m -- Drives qriterS.m driveQRR.m -- Drives qriterR.m driveQRRS.m -- Drives qriterRS.m qrstep.m -- Basic shifted QR step. Applies a single real or a complex conjugate pair using a double shift staying in real arithmetic. qriter.m -- Performs the shifted QR iteration on a real square matrix and displayes the convergence of the subdiagonal elements graphically. Diminishing shades of blue are proportional to size of the subdiagonal element. Displays quasi-triangular form as convergence progresses. qriterS.m -- Performs the shifted QR iteration on a real symmetric matrix and displayes the convergence of the offdiagonal elements graphically. Diminishing shades of blue are proportional to size of the subdiagonal element. Displays diagonal form as convergence progresses. qriterR.m -- Performs the shifted QR iteration on a real square matrix using the implicit polynomial restart strategy. Displayes the convergence of the vector of Ritz estimates and the Hessenberg form of the leading m by m block graphically. Diminishing shades of blue are proportional to size of the subdiagonal elements and the Ritz estimates. Eigenvalues of the leading k by k block shown in the dashed line square converge to k eigenvalues of largest real part. qriterRS.m -- Performs the shifted QR iteration on a real symmetric matrix using the implicit polynomial restart strategy. Displayes the convergence of the vector of Ritz estimates and the tridiagonal form of the leading m by m block graphically. Diminishing shades of blue are proportional to size of the subdiagonal elements and the Ritz estimates. Eigenvalues of the leading k by k block shown in the dashed line square converge to k eigenvalues of largest real part. bluemap.m -- Sets color-map for these graphical displays driveIRA.m -- Drives Iram, edit to change shift selection Iram.m -- Implicitly restarted Arnoldi method. Computes a selected set of eigenvalues based upon a user specification. Returns a partial real Schur decompostion. Includes adjusted boundary (k <- k+4, m <- m+4). Iram1.m -- Same as Iram but does not include adjusted boundary. Both are basic implementations. Neither include deflation or moving boundary in the shift selection and application. Arnold.m -- a variant of ArnoldiC. Allows extension of a k-step Arnoldi factorization to a new one of length m > k. select_shifts.m -- Shift selection routine for Iram to implement users specification for eigenvalues of largest or smallest real part, largest magnitude, largest or smallest algebraic driveIRA_Plt.m -- Drives Iram_Plt.m which illustrates convergence of Ritz estimates in the implicitly restarted Arnoldi method (IRAM). Displayes the convergence of the vector of Ritz estimates and the Hessenberg form of the leading m by m block graphically. Diminishing shades of blue are proportional to size of the subdiagonal elements and the Ritz estimates. Eigenvalues of the leading k by k block shown in the dashed line square converge to k eigenvalues of largest real part. driveIRA_Cnv.m -- Drives Iram_Cnv.m which illustrates convergence of Ritz values in IRAM to selected set of eigenvalues ('LR' is default) Light blue dots are the shifts that were applied througout the iteration. Dark blue dots (deeper shade as iteration proceeds) represent the "wanted" ritz values. Converged Ritz values are circled in red on completion. driveIRA_SI.m -- Drives Shift-Invert IRAM. Displays same information as Iram_Plt.m only with A replaced by (A - sigma I)^{-1}. In a second plot it also shows the converged Ritz values as red circles over the eigenvalues of A (shown as black +'s) and the shift in green with a cyan dashed circle centered at sigma and enclosing the converged Ritz values. Right end or Center can be selected. Iram_Plt.m -- IRAM method with plot display included. See driveIRA_Plt.m above for description. Iram_Cnv.m -- IRAM method with plot display included. See driveIRA_Cnv.m above for description. Gmres.m -- GMRES Efficient solve of min norm(e_1 - Hy) using 2 by 2 orthogonal transformations and updating. Gmres0.m -- GMRES using an explicit call to ArnoldiC straightforward solve of min norm(e_1 - Hy) driveGM0.m -- Drives Gmres0 on series of realated problems. Illustrates GMRES convergence, roots of GMRES vs FOM polynomials, plots log(abs(P)) over region containg eigenvalues of A where P is the GMRES polynomial. driveGMLU -- This code illustrates straight GMRES vs Preconditioned GMRES Center band and ILU are options for preconditioner. Assumes files sherman2.mtx sherman2_rhs1.mtx from Matrix Market are in the session directory. compLinSlvrs.m -- This code compares the nonsymmetric iterative solvers from Matlab: gmres, gmres5, bicgstab, bicg, qmr, cgs Assumes files sherman2.mtx sherman2_rhs1.mtx from Matrix Market are in the session directory. Hump.m -- This code illustrates the behavior of Jacobi, Gauss-Seidel and SOR on normal and also on non-normal matrices. Illustrates the "Hump" phenomenon on a highly non-normal problems (initial transient growth observed before predicted asymptotic convergence rate attained.)