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. | |
| 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 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 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. |
Thomas Rey 
You must be logged in to post a comment.