2013/2014

Spring 2014: Math 401 (Applications of Linear Algebra)
Preliminary Grades Spring 2014 (05/01)

  • Schedule: Tuesday, Thursday, 12:30pm-1:45pm (MTH 0303).
  • Textbook: Linear Algebra and its Applications, 4th Edition, by G. Strang. Published by Thomson Publishing. ISBN: 0030105676.
  • Office Hours: Tuesday: 11:00-12:00 AM, Thursday 2:00 PM-3:00 PM.
  • Description of the course: Various applications of linear algebra: matrix methods as applied to finite Markov chains, random walk, incidence matrices, graphs and directed graphs, networks, Google PageRank, heat equation…
  • Grades: (May be subject to change) 20% for homeworks (4 planned), 20% for numerical projects (2 or 3 planned), 10% for quizzes, 15% for 1st midterm, 15% for 2nd midterm, 20% for the final exam. For each homework assignment, only a random selection of exercises will be graded. Letter grades will be based on the accumulated points at the end of the semester, according to the following scheme: 90%-A; 80%-B; 70%-C; 50%-D; less than 50%-F.
  • Homework : There will be homework assignments (mostly biweekly) and 2-3 short numerical projects to complete. No late homework will be accepted (but early ones are welcome).
  • Examinations : There will be 2 midterm plus a final exam.
  • Expectations : Students are expected to understand some important, basic concepts of linear algebra. This implies both a good knowledge of the theory and the ability to use it to solve practical problems or implement the methods numerically.
  • Learning Assistance Service : If you are experiencing difficulties in keeping up with the academic demands of this course, contact the Learning Assistance Service, 2202 Shoemaker Building, 301-314-7693. Their educational counselors can help with time management, reading, math learning skills, note-taking and exam preparation skills. All their services are free to UM students.
Week Chapter
1 (Jan. 27-31) Section 1.1 & 1.2
2 (Feb. 3-7) Section 1.4
3 (Feb. 10-14) Section 1.3 and 1.5
4 (Feb. 17-21) Section 1.6 and 1.7
4 (Feb. 24-28) Section 1.7 (Centered finite differences)
5 (Mar. 3-7) Section 3.5 (Discrete Fourier Transform)
6 (Mar. 10-14) Section 4.1-4.2 (Construction of the determinant)
7 (Mar. 24-28) Exercises on determinant (Section 4.3) and introduction to eigenvalue problems (Google Pagerank)
8 (Mar. 31-Apr. 4) Exercises session and Midterm
9 (Apr. 7-11) Eigenvalues, eigenvectors and introduction to diagonalization (Section 5.1)
10 (Apr. 14-18) Diagonalization and discrete dynamical systems (Sections 5.2 and 5.3)
11 (Apr. 21-25) Discrete dynamical systems, power method and QR method (Sections 5.3 and 7.3)
12 (Apr. 28-May 2) Markov matrices (section 5.4)
13 (May 5-9) No class this week
14 May 12-13 Last week: practice session

Examinations

In the homework assignments, some bonus points will be given for proper justifications of the answers (even when it is not asked explicitely).

Type Content Due date
Quizz 1 LU decomposition and complexity. Solution. 02/13/2013 02/18/2013
Homework 1 section 1.2: 3; section 1.3: 10, 27; section 1.4: 2, 4, 22, 39; section 1.5: 2, 29; bonus exercises (not mandatory but will give bonus points), section 1.6: 6, 27. 02/18/2014
Quizz 2 LU decomposition, approximate Laplace-Poisson problem, rounding errors 03/04/2014
Homework 2 Section 1.7: 2, 3, 5, 6, 7 ; review exercises: 1.12, 1.14, 1.27 03/06/2014
Midterm
Everything we did since the beginning 04/03/2013
Homework 3 Subject. Solution. 04/17/2014
Quizz 3
Eigenvalues and eigenvectors. Solution 04/15/2018

Numerical project assignment 1

The projects consists in writing a code implementing the corresponding algorithm for one of the following subjects. Students can work in small teams (up to 2 people) and choose any mathematics related language (except perl).
The final project has to be submitted by e-mail to my address before the deadline. Each submission should recall in the e-mail the names of the students having worked on it and the subject chosen. To each e-mail should be attached the source code and a short report (Latex, word, pdf…). The report should describe summarily how the algorithm was implemented, the problem encountered (if any) during the development, how can I test it and the main conclusion (typically a few pages are more than enough).

Here are some Python examples showing you the type of project I would like to see. Of course, I am using in these examples some language routines such as solve(), solve_triangular() or fft(). These are the core of the projects, and I want you to code them explicitely.

  • Efficiency of elimination/substitution for solving the Poisson problem:  Example 1;
  • Sound compression (very basic) using Discrete Fourier Transform filtering: Example 2.
Completion before March 28th
Subject 1 Write a program which given an integer n and a function f solve the n points finite-difference approximation (as studied in class) of the Poisson-Laplace problem
PL
using the LU decomposition of the Laplace matrix (and then forward and backward substitution).
You can then compare when possible the approximate and the exact solution of the problem.
The use of existing language-dependent routines performing the same role (such as numpy.solve() in Python) is of course prohibited.
Subject 2 Write a program which to a given matrix A (possibly non-square) as entry returns its LU decomposition or an error when (or if) this is not possible. Test the efficiency of the algorithm on square random matrices by comparing its execution time with the size of the matrix.
The use of existing language-dependent routines performing the same role (such as linalg.lu(A) in Python) is of course prohibited.
Subject 3 Find about the Gauss-Seidel method to solve linear systems. Write a program which given a square matrix A, a vector y, an initial vector z and a number n as entries returns the vector x approximate solution to Ax=y after n steps of the method starting from z.

Numerical project assignment 2

The projects consists in writing a code implementing the corresponding algorithm for one of the following subjects. Students can work in small teams (up to 2 people) and choose any mathematics related language (except perl).
The final project has to be submitted by e-mail to my address before the deadline. Each submission should recall in the e-mail the names of the students having worked on it and the subject chosen. To each e-mail should be attached the source code and a short report (Latex, word, pdf…). The report should describe summarily how the algorithm was implemented, the problem encountered (if any) during the development, how can I test it and the main conclusion (typically a few pages are more than enough).

Completion before May the 2nd
Subject 1 Find out about the power method. Write a program which to a given square matrix A as entry returns an approximation of its biggest eigenvalue, along with an approximation of its associated eigenvector. In the case where A is invertible, the program can also returns the smallest eigenvalue.
The use of existing language-dependent routines performing the same role (such as numpy.linalg.eig() in Python) is of course prohibited.
Subject 2 Write a program which to a given square matrix A as entry returns its determinant using two different algorithms. Test the efficiency of the algorithms on random matrices by plotting its execution time with respect to the size of the matrix.
The use of existing language-dependent routines performing the same role (such as linalg.det(A) in Python) is prohibited for your project, but you can also plot on your efficency graph the execution time of the machine version.
Subject 3 Find out about the QR method for computing all the eigenvalues of a matrix. Write a program which to a given square matrix A as entry returns a matrix whose diagonal contains all the eigenvalues of A. Test it on various A to show that it works. What is its observed efficiency?
For this subject, you are allowed to use an existing routine to compute the QR decomposition of a square matrix, because we have not seen it in class.

Fall 2013: Math 401 (Applications of Linear Algebra)

  • Schedule: Monday, Wednesday, Friday, 10:00am-10:50am (MTH 0407).
  • Textbook: Linear Algebra and its Applications, 4th Edition, by G. Strang. Published by Thomson Publishing. ISBN: 0030105676.
  • Office Hours: Monday 1:00-2:00 PM, Wednesday, 3:30am-4:30 PM.
  • Description of the course: Various applications of linear algebra: theory of finite games, linear programming, matrix methods as applied to finite Markov chains, random walk, incidence matrices, graphs and directed graphs, networks, transportation problems.
  • Grades: (May be subject to change) 20% for homeworks (4 planned), 20% for numerical projects (2 or 3 planned), 10% for quizzes, 15% for 1st midterm, 15% for 2nd midterm, 20% for the final exam. For each homework assignment, only a random selection of exercises will be graded. Letter grades will be based on the accumulated points at the end of the semester, according to the following scheme: 90%-A; 80%-B; 70%-C; 50%-D; less than 50%-F.
  • Homework : There will be homework assignments (mostly biweekly) and 2-3 short numerical projects to complete. The lowest homework grade will be dropped. No late homework will be accepted (but early ones are welcome).
  • Examinations : There will be 2 midterm plus a final exam.
  • Expectations : Students are expected to understand some important, basic concepts of linear algebra. This implies both a good knowledge of the theory and the ability to use it to solve practical problems or implement the methods numerically.
  • Learning Assistance Service : If you are experiencing difficulties in keeping up with the academic demands of this course, contact the Learning Assistance Service, 2202 Shoemaker Building, 301-314-7693. Their educational counselors can help with time management, reading, math learning skills, note-taking and exam preparation skills. All their services are free to UM students.

Reading

Week Chapter
1 (Sept. 2-7) Section 1.1 & 1.2
2 (Sept. 9 – 13) Section 1.3 & 1.4
3 (Sept. 16 – 20) Section 1.7
4 (Sept. 23 – 27) Section 1.6
5 (Sept. 30 – Oct. 4) Section 4.1 & 4.2
6 (Oct. 7 – Oct. 11) Section 4.3
7 (Oct. 14 – Oct. 18) Exam practicing
6 (Oct. 21 – Oct. 25) Section 4 Review exercices & Beginning of Section 5.1
7 (Oct. 28 – Nov. 1) Section 5.1
8 (Nov. 4 – Nov. 8) Section 5.2
9 (Nov. 11 – Nov. 15) Section 5.2 + Midterm 2 revisions
10 (Nov. 18 – Nov. 22) Midterm 2 (Monday) + Section 5.3 + Google’s Pagerank Algorithm
11 (Nov. 25 – Nov. 26) Google’s Pagerank Algorithm + no class on Wednesday (Thanksgiving)

Examinations

In the homework assignments, some bonus points will be given for proper justifications of the answers (even when it is not asked explicitely).

Type Content Due date
Homework 1 Section 1.3: 10, 13, 17, 24; section 1.4: 6, 7, 20, 31, 33, 43; section 1.5: 4, 30. 09/20/2013
Quizz 1 LU decomposition and complexity 09/23/2013
Homework 2 Section 1.7: 2, 3, 4, 5, 6; review exercises: 1.12, 1.20, 1.22, 1.29 10/04/2013
Quizz 2 PA=LU decomposition with partial pivoting (section 1.6 and 1.7) and the beginning of determinant (section 4.1 and 4.2) 10/11/2013
Midterm 1 Everything we did since the beginning 10/18/2013
Homework 3 Eigenvalues and eigenvectors, beginning of diagonalization. 11/11/2013
Midterm 2 Whole Chapter 4 and Chapter 5, Section 1 and 2 11/18/2013

Numerical project assignment 1

The projects consists in writing a code implementing the corresponding algorithm. Students can work in small teams (up to 2 people) and choose any mathematics related language (except perl). There are two deadlines for each project assignment. The latest one is the date at which the project must be completed and submitted to me. The first one is the date before which students must decide on their project and the composition of their team. Each team has to send me an e-mail before the first date (with all members of the team in copy) indicating their choice and the composition of the team.
The final project has to be submitted by e-mail to my address. Each submission should recall in the e-mail the names of the students having worked on it and the subject chosen. To each e-mail should be attached the source code and a short report (Latex, word, pdf…). The report should describe summarily how the algorithm was implemented, the problem encountered (if any) during the development, how can I test it and the main conclusion (typically a few pages are more than enough).

Choice before October 16th, completion before October 28th
Subject 1 Write a program which given an integer n and a function f solve the n points finite-difference approximation (as studied in class) of the Poisson-Laplace problem
PL
using the LU decomposition of the Laplace matrix (and then forward and backward substitution).
You can then compare when possible the approximate and the exact solution of the problem.
The use of existing language-dependent routines performing the same role (such as numpy.solve() in Python) is of course prohibited.
Subject 2 Write a program which to a given matrix A (possibly non-square) as entry returns its LU decomposition or an error when (or if) this is not possible. Test the efficiency of the algorithm on square random matrices by comparing its execution time with the size of the matrix.
The use of existing language-dependent routines performing the same role (such as linalg.lu(A) in Python) is of course prohibited.
Subject 3 Find about the Gauss-Seidel method to solve linear systems. Write a program which given a square matrix A, a vector y, an initial vector z and a number n as entries returns the vector x approximate solution to Ax=y after n steps of the method starting from z.

Numerical project assignment 2

The projects consists in writing a code implementing the corresponding algorithm. Students can work in small teams (up to 2 people) and choose any mathematics related language (except perl). There are two deadlines for each project assignment. The latest one is the date at which the project must be completed and submitted to me. The first one is the date before which students must decide on their project and the composition of their team. Each team has to send me an e-mail before the first date (with all members of the team in copy) indicating their choice and the composition of the team.
The final project has to be submitted by e-mail to my address. Each submission should recall in the e-mail the names of the students having worked on it and the subject chosen. To each e-mail should be attached the source code and a short report (Latex, word, pdf…). The report should describe summarily how the algorithm was implemented, the problem encountered (if any) during the development, how can I test it and the main conclusion (typically a few pages are more than enough).

Choice before November 20th, completion before December 2nd
Subject 1 Find out about the power method. Write a program which to a given square matrix A as entry returns an approximation of its biggest eigenvalue, along with an approximation of its associated eigenvector. In the case where A is invertible, the program can also returns the smallest eigenvalue.
The use of existing language-dependent routines performing the same role (such as numpy.linalg.eig() in Python) is of course prohibited.
Subject 2 Write a program which to a given square matrix A as entry returns its determinant. Test the efficiency of the algorithm on random matrices by plotting its execution time with respect to the size of the matrix.
The use of existing language-dependent routines performing the same role (such as linalg.det(A) in Python) is prohibited for your project, but you can also plot on your efficency graph the execution time of the machine version.