ARPACK

CAAM 551: Advanced Numerical Linear Algebra

Matlab Code

Codes and Descriptions

Dense LU decompostions for Ax = b

LUfac.m, LUfacP.m, LUfacC.m, and LUfacR.m

Dense Cholesky decompostion for Ax = b

Chol.m

Matlab Sparse Cholesky Demo -- Compare Orderings

Matlab Sparse Unsymmetric LU -- Compare Orderings

UNsparsedem.m compares LU and UMFpack LU
UNsparsedem.m threshold pivoting comparison

QR_factorization: Compare MGS, CGS, CGS w/ refinement

CGStestN.m, CGStestF.m,
QRcgs.m, QRmgs.m, QRcgsF.m

QR_factorization and Least Squares via Row-wise Givens Method

Sparse QR_factorization motivating example

SparseQRex.m, evalB.m

Numerical Effects of Sign Choice for Householder Transformation

HHbad.m, driveHHB.m, Illustrates loss of orthogonality and accuracy when wrong sign choice is made
HHgood.m, driveHHG.m, Illustrates correct choice of sign cures numerical problems

QR_factorization via Householder's Method

Heat test problem for regularization exercise

Heat1.m,

Illustration of perturbation bounds for Ax = b,

Shows || x1 - x||/||x|| < K(A)||b1 - b||/||b||.

EQNcondemo.m,

Illustration of perturbation bounds for min ||b - Ax ||

Shows || x1 - x||/||x|| < (K(A)/cos(theta))||b1 - b||/||b||.

Demonstrates that condition of Normal Equations (NEQ) is the square of the condition number of A

Shows || x1 - x||/||x|| < (K(A)^2)||A'(b1 - b)||/||A'b||.

NEQcondemo.m

Illustrations of best rank k SVD approximation

Rank k image reconstruction of a JPEG image
reconstruct.m
Dimension Reduction of Dynamical Systems
pod1.m
pod2.m

Basic Iterative Methods for Ax = b

Illustrates convergence history ||G^k|| non-normal G
powersR.m
Illustrates convergence Jacobi,G-S, SOR history ||G^k(x0 -x)|| non-normal G
Hump.m
Illustrates effects of non-normal G on convergence history showing "the Hump"

Krylov Projection and Basic Arnoldi Factorization

krylov.m
Illustrates when [V,R] = qr(K,0) is computed where K = [b, Ab,..., A^(k-1)b] is obtained directly from the power sequence fails numerically. H = V'AV is not Hessenberg and AV .ne. VH + fe_k'.
Arnoldi.m, ArnoldiC.m
Illustrates loss orthogonality with CGS (driveA) and full orthogonaltiy with CGS followed by iterative refinement (driveAC)
driveA.m, driveAC.m,

GMRES method and comparison

Gmres0.m
Basic GMRES code
Gmres.m
GMRES code using Givens rotations to update LS soln and residual
driveGmres_Fom.m, Gmres_Fom.m
Illustrates convergence of GMRES and FOM on various normal and non-normal cases
Shows GMRES polynomial surface related to spectrum of A
normal_vs_non.m
Compares Eigenvalue Perturbations Normal vs Non-normal
compLinSlvrs.m
Compares performance of various Kryov based solvers

Preconditioned Gmres

GmresP.m
GMRES code that applies left pre-conditioning with M = LU in factored form
driveGMLU.m
Demonstrates performance of pre-conditioned vs unconditioned GMRES

Basic Iterative Eigenvalue Methods

pow.m, pow_inf.m, pow_rq.m, and driveP.m

Ritz Value Convergence

eigconv.m, ritzest.m

Effect of Polynomial Restarting

polyR.m

Gui: Graphic Illustration of Ritz Value Convergence

eigenui.m, eigen_update.m

Simple Lanczos Process: Breakdown

Ritz value behavior in Lanczos

Graphic Illustration of QR-convergence

driveQR.m, driveQRS.m, driveQRR.m, and driveQRRS.m
qrstep.m,
qriter.m,
qriterS.m,
qriterR.m,
qriterRS.m
bluemap.m

Implicitly Restarted Arnoldi (IRA)

Graphic Illustration of IRA Hessenberg convergence

driveIRA_Cnv.m

Graphic Illustration of IRA exact shift selection

and resulting filter polynomial surface in relation

to the spectrum of the matrix

driveIRA_Polyshow.m, Shows ritz values and exact shift selection in IRAM
driveIRA_SI_Polyshow.m, Shows ritz values and exact shift selection in Shift Invert IRAM
Iram_Polyshow.m, Iram_SI_Polyshow.m,