A short introduction to matvec algorithms
Summary
This is the first installment in a short series on "matvec algorithms," which are algorithms for linear algebraic problems that primarily use matrix-vector products rather than full matrix operations such as matrix-matrix multiplication.
CollapseLearning Goals
- The student will learn the difference between "dense" and "sparse" matrices.
- The student will learn other important matrix structures, such as bandedness and low-rank structure.
- The student will learn useful sparse matrix methods in MATLAB, such as the sparse and eigs commands.
- The student will learn some advanced algorithms in numerical analysis, such as the power method, Krylov subspace methods, and the Barnes-Hut algorithm
- The student will encounter interesting applications to network analysis, vibrational modes, and gravity simulations.
- The student will learn other important matrix structures, such as bandedness and low-rank structure.
- The student will learn useful sparse matrix methods in MATLAB, such as the sparse and eigs commands.
- The student will learn some advanced algorithms in numerical analysis, such as the power method, Krylov subspace methods, and the Barnes-Hut algorithm
- The student will encounter interesting applications to network analysis, vibrational modes, and gravity simulations.
Context for Use
- It is assumed the student is familiar with basic MATLAB syntax and linear algebra. Some experience with scientific algorithms is also helpful.
- This is intended as an independent activity to learn about data-sparse or structured linear algebraic computations.
- The material may be useful for adaptation into a problem set in a linear algebra, numerical linear algebra, or numerical methods course.
- This is intended as an independent activity to learn about data-sparse or structured linear algebraic computations.
- The material may be useful for adaptation into a problem set in a linear algebra, numerical linear algebra, or numerical methods course.
Description and Teaching Materials
The MATLAB publish function was used to generate these materials as pdf files, and all algorithms and plotting tools are implemented in MATLAB. Below, we upload the original .m files for the introduction and the first activity (network rankings), as well as a publishing function and xml file for formatting the output. We also attach the output as a single pdf. This is a draft of the final result, which will include two further activities.
MATLAB source for introduction (Matlab File 20kB Oct6 26)
MATLAB source for activity 1 on network rankings (Matlab File 17kB Oct6 26)
Publish function to render as pdf (Matlab File 5kB Oct6 26)
xsl stylesheet for publish function ( 17kB Oct6 26)
Introduction and first activity for introduction to matvec algorithms (Acrobat (PDF) 2.2MB Oct6 26)
MATLAB source for introduction (Matlab File 20kB Oct6 26)
MATLAB source for activity 1 on network rankings (Matlab File 17kB Oct6 26)
Publish function to render as pdf (Matlab File 5kB Oct6 26)
xsl stylesheet for publish function ( 17kB Oct6 26)
Introduction and first activity for introduction to matvec algorithms (Acrobat (PDF) 2.2MB Oct6 26)
Teaching Notes and Tips
This is intended as an independent reading to supplement a course on numerical linear algebra. It includes exercises that could be included on a problem set at the end of each section.
Share your modifications and improvements to this activity through the Community Contribution Tool »
Assessment
Running the code presented in the writeup independently to recreate the figures and completing the exercises at the end of each section.