Advanced Search

    Readings

    The primary textbook for the course is:

    [NLA]= Amazon logo Trefethen, Lloyd N., and David Bau III. Numerical Linear Algebra. Society for Industrial and Applied Mathematics, 1997. ISBN: 9780898713619.

    Additional readings:

    [Linear] = Amazon logo Barrett, et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1993. ISBN: 9780898713282.

    [Algebraic]= Amazon logo Bai, et al. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2000. ISBN: 9780898714715.

    SES # TOPICS READINGS
    1 Key concerns of numerical methods

    [NLA] Lecture 20.

    Amazon logo Further reading: If you need to review linear algebra, review chapters 1-3. If you don't have the linear algebra prerequisite review chapters 1-6 of Strang, Gilbert. Introduction to Linear Algebra, 4th Edition. Wellesley-Cambridge Press, 2009. ISBN: 9780980232714.
    2 Performance: Arithmetic vs. memory

    "Introduction to Memory Locality." Wikipedia.

    Information on Automatically Tuned Linear Algebra Software (ATLAS).

    Frigo, Matteo, et al. "Cache-Oblivious Algorithms." Proceedings of the 40th Annual Symposium on Foundations of Computer Science. 1999.

    Moler, Cleve. "MATLAB Incorporates LAPACK: Increasing the Speed and Capabilities of Matrix Computation." MATLAB News & Notes. Winter 2000.
    3 Memory optimization and cache obliviousness

    [NLA] Lecture 20.

    Frigo, Matteo, et al. "Cache-Oblivious Algorithms." Proceedings of the 40th Annual Symposium on Foundations of Computer Science. 1999.

    ———. "Register Allocation in Kernel Generators." Talk given July 9, 2007. (This resource may not render correctly in a screen reader.PDF)

    Information on Automatically Tuned Linear Algebra Software (ATLAS).
    4 Accuracy and floating-point arithmetic

    [NLA] Lectures 13, and 20.

    D'Alberto, Paolo, and Alexandru Nicolau. "Using Recursion to Boost ATLAS's Performance." High Performance Computing 4759 (2008): 142-151.

    "Strassen Algorithm." Wikipedia.

    Goldberg, David. "What Every Computer Scientist Should Know About Floating Point Arithmetic." ACM Computing Surveys 23, no. 1 (1991): 5-48.

    Kahan, W., and Joseph D. Darcy. "How Java's Floating-Point Hurts Everyone Everywhere." Paper presented at ACM Workshop on Java for High-Performance Network Computing. Stanford University, 1998. (This resource may not render correctly in a screen reader.PDF)
    5 Floating-point and numerical stability [NLA] Lectures 13, and 14.
    6 Backwards stability of summation, norms [NLA] Lectures 14, 15, and 3.
    7 Condition numbers and eigenvalues

    [NLA] Lectures 12, 14, 15, and 24.

    See linear algebra textbook for a review of eigenvalue problems, especially Hermitian/real-symmetric ones.
    8 The singular-value decomposition [NLA] Lectures 4, 5, and 11.
    9 Least-square problems and QR factors [NLA] Lectures 7, and 8.
    10 Gram-Schmidt stability and householder QR [NLA] Lectures 7,8, 10, and 16.
    11 Householder, Gaussian, and Cholesky factorization [NLA] Lectures 10, 16, 21, 22, and 23.
    12 Eigenproblems, characteristic polynomials, and Shur factors [NLA] Lectures 24, and 25.
    13 Hessenberg factorization and its applications, power methods

    [NLA] Lecture 27.

    Notes on power/inverse/Rayleigh iteration.
    14 QR iteration for eigenproblems

    [NLA] Lectures 28-30.

    Prof. Per-Olof Persson's 2007 notes on QR algorithm Part I and Part II and eigenvalue algorithms. (PDF I) (PDF II) (PDF III)
    15 Overview of iterative and sparse solvers

    [NLA] Lectures 31, and 32.

    [Linear]

    [Algebraic]
    16 Arnoldi and Lanczos iterations [NLA] Lectures 33, 34, and 36.
    17 Restarting Lanczos iterations Amazon logo Lehoucq, R., and D. Sorensen. "Implicitly Restarted Lanczos Method." In Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Edited by Zhaojun Bai et al. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2000. ISBN: 9780898714715.
    18 GMRES and MINRES

    [NLA] Lectures 35, and 39.

    [Linear]

    Van Der Vorst, Henk. "Lecture Notes on Iterative Methods." (Second section, starting with GMRES).

    Embree, Mark. "Restarted GMRES Dynamics." Householder Symposium XV. June 21, 2002. (This resource may not render correctly in a screen reader.PDF - 2.6MB)

    Sleijpen, Gerald L. G., Henk A. Van Der Vorst, and Jan Modersitzki. "Differences in the Effects of Rounding Errors in Krylov Solvers For Symmetric Indefinite Linear Systems." 1999.

    Shewchuk, Jonathan Richard. "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain." August 4, 1994. (This resource may not render correctly in a screen reader.PDF)
    19 Steepest-descent and conjugate-gradient methods Shewchuk, Jonathan Richard. "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain." August 4, 1994. (This resource may not render correctly in a screen reader.PDF)
    20 Preconditioning and condition numbers of PDE-like matrices [Linear]. Preconditioners Chapter.
    21 Biconjugate-gradient methods, sparse-direct solvers

    [Linear]. Preconditioners Chapter.

    Van Der Vorst, Henk. "Lecture notes on Iterative Methods." (Second section, starting with GMRES).

    Khaira, Manpreet S., Gary L. Miller, and Thomas J. Sheffler. "Nested Dissection: A Survey and Comparison of Various Nested Dissection Algorithms." 1992.

    Dongarra. "Direct Solvers for Sparse Matrices."

    Davis, Timothy. "Summary of Available Software for Sparse Direct Methods." March 30, 2009.

    Direct Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics. 2009. [Preview with Google Books]
    22 Nonlinear conjugate gradient, and conjugate-gradient eigensolvers [Linear] Section on preconditioned CG methods for eigenproblems.
    23 Overview of optimization problems No readings.
    24 Adjoint methods and sensitivity analysis No readings.
    25 Adjoint methods for recurrences, CCSA algorithms No readings.
    26 Lagrange dual functions and KKT conditions

    Boyd, Stephen, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Chapter 5.

    "Karush-Kuhn-Tucker Conditions." Wikipedia.
    27 Quasi-Newton methods No readings.
    28 BFGS updates

    "Sherman-Morrison Formula." Wikipedia.

    "Quasi-Newton Method." Wikipedia.

    "BFGS Method." Wikipedia.

    Dennis, Jr., J. E. "A New Derivation of Symmetric Positive Definite Secant Updates." University of Colorado at Boulder. August 1980. (This resource may not render correctly in a screen reader.PDF - 1.4MB)

    O'Leary, Dianne P., and A. Yeremin. "The Linear Algebra of Block Quasi-Newton Algorithms." Linear Algebra and Its Applications 212/213 (1994): 153-168. (This resource may not render correctly in a screen reader.PDF)
    29 Derivative-free optimization: Linear and quadratic models

    Amazon logo Conn, Andrew R., Katya Scheinberg, and Luis N. Vicente. Introduction to Derivative-Free Optimization. Society for Industrial and Applied Mathematics, 2009. ISBN: 9780898716689 [Read on Google Books].

    "NLopt Algorithms."
    30 Global optimization and the DIRECT algorithm No readings.
    31 Numerical integration and accuracy of the trapezoidal rule No readings.
    32 Clenshaw-Curtis quadrature No readings.
    33 Chebyshev approximation

    "Chebyshev Polynomials." Wikipedia.

    Boyd, John P. Chebyshev, and Fourier Spectral Methods, 2nd Edition. Dover Publishers, 2001.

    Chebfun: Numerical Computing with Functions. Oxford University Mathematical Institute.

    Trefethen, Lloyd N. "Is Gauss Quadrature Better Than Clenshaw-Curtis?" SIAM Review 50, no. 1 (2008): 67-87.