**ECSE 343 -- Numerical Methods in Engineering** *Winter 2022* - [McGill University](http://www.mcgill.ca) -- Prof. [Derek Nowrouzezahrai](http://www.cim.mcgill.ca/~derek) Students will learn the many ways that computation can be applied to solve complex, mathematically-modeled systems. We will start by focusing on linear systems before moving to more general problems. We will explore different families of numerical methods that can be used to solve these systems and their trade-offs. Finally, students will gain experience with considerations needed when transposing mathematical solutions into computational algorithms on finite precision number systems. Administrative Details ======================== There are two (2) weekly 80-minute lectures on *Tuesdays* and *Thursdays* from 10:05am to 11:25am in *MAASS 10*, and one (1) weekly 110 minute tutorial session on *Fridays* from 11:35am to 1:25pm in *LEA 219*. !!! Tip The fluidity of the COVID situation may necessitate changes to the course and tutorial delivery methods (e.g., online vs. in-person). Please be attentive to University announcements on this matter, all of which will be reiterated during the lectures. Course Overview ================ Engineers often face problems that require modelling an understanding of complex dynamical systems, before simulating the behaviour of these models with modern computational tools. Such a process underlies many real-world engineering challenges, and so building a high level of competence and comfort with the associated mathematical, numerical and computational tools is fundamental to every electrical, computer and software engineers’ training. This course builds atop the foundational continuous and discrete mathematics of our engineering curricula (i.e., differential calculus, statistics), as well as basic expertise in algorithm design and development. Its high-level goal is to bridge concepts from applied mathematics to engineering applications, through the lens of numerical computation. You will code and analyse modern numerical methods, including those used across a variety of domains: electrical engineering, physics-aware robotics systems, computer vision and imaging, and machine learning, to name a few. The course will guide you through the theoretical and practical implications behind each method. You will learn how to move from abstract problem statements, to mathematical models, and finally computational solutions.

_The course syllabus and schedule may be revised during the semester. The latest version is always online here, at_ http://www.cim.mcgill.ca/~derek/ecse343.html Requirements ================================================================================ We outline some high-level requirements and expectations, below. Prerequisites ----------------------------------------------- * [*ECSE 205*: Probability and Statistics for Engineers](https://www.mcgill.ca/study/2019-2020/courses/ecse-205) and * [*COMP 250*: Introduction to Computer Science](https://www.mcgill.ca/study/2019-2020/courses/comp-250) * [*MATH 263*: Ordinary Differential Equations for Engineers](https://www.mcgill.ca/study/2019-2020/courses/math-263) We expect you to be comfortable with multivariate calculus, probability (discrete and continuous) and linear algebra: much of the theory we present in the course will focus on _re-framing_ mathematical constructs through an algorithmic and computational lens. Furthermore, you'll be expected to code your own assignment solutions during this course, and so comfort with data structures and algorithms will be valuable; coding solutions will not require large software engineered solutions, but will rather focus on implementing and testing the core algorithms and numerical methods. This course will afford you the opportunity to become comfortable with vectorized numerical computation using `Python` and `numpy`. Textbook --------------------------------------------------- When appropriate, supplemental recommended readings will be provided during lecture across the following textbooks. !!! Tip You don't __need__ to buy any of these texts to be successful in the course, but some of you may find it helpful. Leveraging *lecture* and *tutorial* time (i.e., consistent attendance, taking notes and asking questions) is much more important for building an understanding and retaining the knowledge you gain. *Scientific Computing: An Introductory Survey* (_Revised 2nd ed._)
by Michael T. Heath ![Recommended Text I](https://my.siam.org/Store/ProductImages/CL80large.jpg width="25%") This text focuses on the core ideas behind fundamental algorithms, rather than a detailed numerical analysis. Problems in mathematical & computational modeling, data analysis, and hands-on engineering examples are presented in a clear and concise style. Readers are guided through the processes of properly formulating any specific problem, carefully choosing an appropriate numerical algorithm to resolve the problem, and interpreting the results of the algorithm. Our course will rely heavily on the exposition and examples provided in _Scientific Computing: An Introductory Survey (Revised Second Edition)_. *Numerical Algorithms:* Methods for Computer Vision, Machine Learning, and Graphics
by Justin Solomon ![Recommended Text II](https://people.csail.mit.edu/jsolomon/assets/bookcover.jpg width="25%")The core concepts in numerical methods for linear and non-linear problems are presented from a similar perspective, with insightful geometric interpretations and diagrams. What most differentiates this book is a bit more of a focus on methods employed in current practice, presenting a more hands-on approach to numerical analysis for modern computer scientists and engineers. Examples vary across many computational tasks, from data processing, computational photography, and physics-based animation. The text does a good job guiding the reader from theoretical insights to numerical modeling and algorithmic design. As with any modern text on the subject, this one covers topics from numerical linear algebra to optimization and differential equations. The text targets an advanced undergraduate and graduate audience, assuming strong foundations in calculus and linear algebra. ![Recommended Text III](https://my.siam.org/Store/ProductImages/CS07large.jpg width="25%") *A First Course in Numerical Methods*
by Uri M. Ascher and Chen Greif This text also balances theoretical concepts with practical knowledge, doing a good job of highlighting the importance of moving from a mathematical formulation of a problem to a computational one. I particularly like the way this text presents the importance of parallelization, cache coherence, and other systems-level details that must be treated by a _designer_ of efficient numerical methods. That being said, those with less experience in advanced undergraduate linear algebra might have a harder time working through some of the more mathematical concepts presented early on the book; that being said, in taking the time to build this background, one becomes much better equipped to work through the rest of the "standard set" of numerical methods presented throughout the book. This text also does a very good job of helping the reader understand the many reasons behind the success and failure of numerical software. MATLAB is treated as a first class citizen in this text, and the transition from MATLAB- to Python-based numerical method development is not a large one. The target audience, as with the Solomon text, is senior undergraduate and beginning graduate level. Equipment --------------------------------------------------- IT has configured lab machines in Trottier with an ECSE 343 development stack. The [first assignment](#Assignments) provides multi-platform instructions for setting up a local development environment, for completing work on a personal machine. Time --------------------------------------------------- Attendance is *strongly encouraged*. Plan to invest *9 hours of work per week*, on average, including lecture and tutorial time. For assignments, start early and schedule appropriately. Attending tutorials with your prepared questions is a good way to skirt avoidable difficulties. Evaluation ===================================================================== Your evaluation is based on Python coding [assignments](#assignments) and a final [group project](#project).

Grading Component
-------------------------------|------------------- Individual Coding Assignments |
70% + 5% bonus
Final Group Project |
Your score will rely on the successful completion of the programming tasks, which will require a strong grasp of the concepts covered during lecture. A breakdown of each of these grading components follows. Coding Assignments **[**70% + 5% bonus**]** ------------------------------------------------------------ We will provide minimal base `Python` code for each assignment. Assignments are to be completed individually. Assignment details will be posted here as the semester progresses. !!! ERROR: Late Policy Failure to submit a (valid) assignment on time will result in a penalty of -25% per day (rounded up to the nearest day). Make as many myCourses submissions as you want: we will only grade the last submission. Exceptional circumstances will be treated as specified in [McGill's Policies on Student Rights and Responsibilities](https://www.mcgill.ca/students/srr/). Assignment handouts will detail the required tasks and submission procedures. Assignment deadlines are all at *11:59pm EST* on their respective due dates. ![Example A0 Output](http://www.cim.mcgill.ca/~derek/ecsex43/a0-thumbnail.png width="32%") **Assignment 0 -- Python & Floating-point [0%+ 5% bonus]**
- Setup your Python 3.7 environment - Floating point, `numpy` and vectorization - Due January 20 - Handout and base code available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A0.md.html) - Base code available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A0_base.py) ![Deconvolution from A1](http://www.cim.mcgill.ca/~derek/ecsex43/a1-thumbnail.png width="32%") **Assignment 1 -- Linear Least Squares [15%]**
- Forward and backward substitution - Normal equations and polynomial fitting - Image deconvolution - Due February 3 - Handout, base code and data available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A1.md.html) - Base code available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A1_base.py) - Data file available [here](http://www.cim.mcgill.ca/~derek/ecsex43/Q3-test-data.npy) ![EM for GMMs from A2](http://www.cim.mcgill.ca/~derek/ecsex43/gmm.png width="25%") **Assignment 2 -- Advanced Model Fitting [15%]**
- Polynomial regression - MLE, MAP, LLS - Expectation-maximization - Gaussian mixture models - Due February 17 - Handout and base code available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A2.md.html) - Base code available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A2_base.py) ![Deconvolution, Round 2](http://www.cim.mcgill.ca/~derek/ecsex43/a1-thumbnail.png width="32%") **Assignment 3 -- Regularization and SVD [20%]**
- 2D image (de)convolution - Explicit regularization - Singular value decomposition - Due March 17 - Handout, base code and data available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A3.md.html) - Base code available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A3_base.py) - Data file available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A3-test-data.npy) ![Fourier is your Friend](http://www.cim.mcgill.ca/~derek/ecsex43/image-blur.png width="32%") **Assignment 4 -- Discrete Fourier Transform [20%]**
- 1D and 2D Discrete Fourier Transform - Convolution and Deconvolution in the Frequency Domain - Frequency-space Regularization - Due March 31April 7 - Handout, base code and data available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A4.md.html) - Base code available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A4_base.py) - Data file available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A4-test-data.npy) !!! Tip For grading questions please contact our teaching assistant at jithendaraa.subramanian@mail.mcgill.ca .
Final Group Project **[**30%**]** ------------------------------------------------------------ There is no final exam for the course. Instead, students will work in _groups of two_ (2) on an open-ended numerical problem. Unlike the assignments, we will only provide a problem statement and some high-level optional guidelines. Groups will be expected to formulate a sufficiently well-motivated mathematical model for their problem, select (at least one) numerical method to solve it, and to design and conduct the experiments and analyses needed to convincingly demonstrate the effectiveness of their solution and any conclusions they draw. Groups will be responsible for documenting the entirety of their work, in a clear and (ideally) concise report (i.e., quality over quantity; maximum of three pages). The online project handout is available [here](http://www.cim.mcgill.ca/~derek/ecsex43/Project.md.html). Extensions, Solutions and Absences ------------------------------------------------------------ Begin assignments early and review your corrected assignments in order to assess any errors along the way. We will **not provide source code solutions** for assignments -- it is your responsibility to make sure your code is correct, consulting with the TAs **during the tutorial sessions**, if necessary. As [outlined earlier](#AssignmentLatePolicy), late assignments will result in a time-based late penalty. The [course schedule](#CourseSchedule) will be updated as the semester progresses. We suggest you cross-reference the schedule with the [assignment deadlines](#AssignmentDeadlines) to avoid missing deadlines -- especially if you have **planned absences**. Start work early each week to minimize the impact of **unplanned absences**. !!! ERROR: Online Solutions Don't post your solutions online. Refer to the [collaboration & plagiarism policies](#CollaborationPolicy) below. Course Topics ===================================================================== The course combines slide-based lectures, hands-on tutorials, take-home programming assignments and a final group project. !!! Tip The fluidity of the COVID situation may necessitate changes to the course topics, deliverables, deadlines and/or the grading scheme. Teaching staff will communicate any such changes, updating this website accordingly. List of Topics ----------------------------------------------- * Floating point number systems and computational numerics * Review: linear algebra, series expansions * Linear systems * Intepretations of linear systems of equations * Gaussian elimination * LU Factorization * Conditioning and regularization * Least squares and QR decomposition * Review: probability * Probabilistic models * Maximum likelihood estimation * Maximum a posteriori estimation * Expectation maximization * Eigendecomposition, applications and singular value decomposition * Non-linear systems of equations * Root finding problems and methods * 1D optimization * Multivariate optimization * Gradient descent * Review: Fourier series and transforms * Discrete Fourier transform and applications * Fast Fourier transform * Numerical integration * Interpolation Tentative Course Schedule -----------------------------------------------
: 0 -- Administration & Floating Point - Course administration - Course outline and schedule - Grading policies - Overview of floating point number systems - IEEE floating point - Rounding and discretization error - Forward vs. backward error - Conditioning: forward vs. backward error - Absolute vs. relative error : 0 -- Floating Point - _Continuation of previous lecture topics_ : 1a -- Linear Algebra: Review - Review - Vectors - Vector spaces - Measures: norms and inner products - Basis and Span - Canonical linear basis - Orthonormal basis - Matrices as linear bases : 1a -- Linear Algebra: Review
(A0 out) - Review - Linear maps - Transformations - Inverse transforms - Methodological case study: 2D rotation - Linear transformation zoo - Linear transform composition - Revisiting the determinant - Translation: motivating homogenous coordinates - Affine maps - Composition - From 2D to 3D to $n$-D : 1b -- Solving simple linear systems - Review of linear systems of equations - Algebraic solution (in 2D) - Geometric solution (in 2D) - Matrix solution (in 2D) - Existence conditions for inversion : 1b -- LU Factorization
(A0 due) - Gaussian elimination - forward/backward substitution - numerical issues - Elementary matrix operations and their inverses - Pivoting (partial vs. full) - LU performance - Solving systems with LU - Example #1: polynomial regression - Example #2: image deconvolution : 2a -- Linear Systems: Conditioning
(A1 out) - Induced matrix norms - Solving perturbed linear systems - Condition number - Conditioning of simple problems : 2b -- Least Squares & Variants - Overdetermined systems - Least-squares and the normal equations - Weighted least squares : 2c -- QR Decomposition & Regularization - Total least squares - Conditioning of the normal equations - QR Factorization - Tikhonov regularization - applied to normal equations - applied to QR decompositions : 3a -- Probability - Review - Experiment, sample space, event - Discrete random variables - Probability mass function - Conditional probability - Total probability - Bayes' theorem - Continuous domain - Probability density function : 3b -- Maximum Likelihood Estimation - Explicit model of noise - Relationship between MLE and Least-squares - Non-zero mean : 3c -- Maximum A Posteriori Estimation
(A1 due) & (A2 out) - Prior distributions on model parameters - Data- vs. Model-dependence : 3d -- Maximum A Posteriori Estimation - Relationship between LLS, MLE and MAP : 3d -- Expectation Maximization - Fitting several models : 4a -- Eigendecomposition - Eigenvectors and eigenvalues - Eigendecomposition - general case and symmetric matrices - Computing eigendecompositions - Power method - Limitations : 4b -- Eigendecomposition Applications - Total least squares : 4c -- Eigendecomposition Applications - Principal components analysis - Solving systems of ODEs : 4c -- Singular Value Decomposition
(A2 due) & (A3 out) : 4c -- Singular Value Decomposition : 4d -- SVD Applications (): Reading Week
(no class) (): Reading Week
(no class) : 5a -- Root Finding - Non-linear systems of equations - Bisection search - Convergence analysis : 5b -- Taylor Series & Convolution Review - Standard Series Expansions - Maclaurin series expansion - Taylor series expansion - Convolutions : 5b -- Advanced Root Finding - Linearizing problems - Higher-order root finding - Newton's method : 5b -- Advanced Root Finding - Higher-order root finding - Evaluating gradients - Secant method - Multivariable root finding - Vector calculus & Multivariable Taylor - Newton's method - Quasi-Newton methods : 5c -- 1D Optimization
(A3 due) & (A4 out) - Root-finding vs. optimization - Convex (and concave) functions - Unimodular functions - Golden section search - Newton's method for 1D optimization : 5d -- Multivariate Optimization - Newton's method for multivariable optimization - Line search - Approximating Hessians - BFGS : 6a -- Fourier - Fourier Series - Fourier Transforms : 6b -- Discrete Fourier Transform - Discrete Fourier Transform - Computing the DFT : 6c -- FFT - Fast Fourier Transform : 7a -- Better Polynomials - Gram Schmidt Orthogonalization - Polynomial Error/Accuracy - Chebyshev nodes : 7a -- Beyond Polynomials - Splines - Radial Basis Functions : 7b -- Numerical Integration - Quadrature rules : Project Options Presentation
(A4 due) & (Project out) - We will review the various group project choices : 7b -- Numerical Integration - Monte Carlo Integration - Variance Reduction - Importance Sampling : 8 -- Gradient Descent - Basic gradient descent - Step size and count - Line search - Solving linear systems with gradient descent - Deriving the optimal step size - Steepest Descent : 8 -- Gradient Descent - Conjugate Gradient (): End
(Project due) - TBD
Collaboration & Plagiarism ===================================================================== *Plagiarism* is an academic offense of misrepresenting authorship. This can result in penalties up to expulsion. It is also possible to plagiarise _your own work_, e.g., by submitting work from another course without proper attribution. **When in doubt, attribute!** We expect you to submit your own work. Assignments are individual tasks. That said, we want to promote an environment where you are comfortable discussing ideas together. **A good rule to follow**: fully understand every solution you submit and only submit code that was written by you. McGill values academic integrity and students should take the time to fully understand the meaning and consequences of cheating, plagiarism and other academic offenses (as defined in the Code of Student Conduct and Disciplinary Procedures -- see [these](www.mcgill.ca/integrity) [two](www.mcgill.ca/students/srr/honest) links). !!! warning: Computational plagiarism detection tools are employed as part of the evaluation procedure in ECSE 343. In accordance with article 15 of the Charter of Students' Rights, students may submit any written or programming components in either French or English. If you have a disability, please advise the [Office for Students with Disabilities](www.mcgill.ca/osd) (514-398-6009) as early in the semester as possible. In the event of circumstances beyond our control, the evaluation scheme as set out above may require modification. Additional policies governing academic issues which affect students can be found in the Handbook on Student Rights and Responsibilities.