**Introduction to Numerical Methods in Electrical Engineering** *Winter 2020* - [McGill University](http://www.mcgill.ca) -- Prof. [Derek Nowrouzezahrai](http://www.cim.mcgill.ca/~derek) This course will highlight the many ways that modern computing platforms can be used to solve complex systems. We will explore mathematical models for a variety of such systems and, in each case, families of numerical methods that can be applied to realize solutions. Administrative Details ======================== There are three (3) weekly 50-minute lectures on *Mondays*, *Wednesdays* and *Fridays* from 11:35am to 12:35pm in *MAASS 10* (held online, during the COVID-19 university closure), and one (1) weekly two-hour tutorial session. The _activity schedule_ (3--2--4) includes 39 hours of lecture, 26 hours of tutorial and 52 hours of self-study. 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/ecse443.html Requirements ================================================================================ We outline some high-level requirements and expectations, below. Prerequisites ----------------------------------------------- * [*ECSE 202*: Introduction to Software Development](https://www.mcgill.ca/study/2019-2020/courses/ecse-202) * [*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 coding quite a bit in this course, and so expertise with data structures, algorithms, and basic software engineering practices will be valuable. Textbook --------------------------------------------------- Supplemental recommended readings will be provided during lecture, across the following textbooks. *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. !!! Tip You don't __need__ to buy any of these texts to be successful in the course, but it can help. Leveraging *lecture* and *tutorial* time (i.e., consistent attendance, taking notes and asking questions) correlates much more with success than exhaustively completing recommended readings. Equipment --------------------------------------------------- You don't need to buy any equipment. IT has configured lab machines in Trottier with an ECSE 443 development stack. The [first assignment](#Assignments) provides multi-platform instructions for setting up a local development environment, if you choose to work on a personal machine. Time --------------------------------------------------- We *strongly encourage* attending every lecture. 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 five (5) [assignments](#assignments) and in-lecture [micro-quizzes](#quizzes).

Grading Component
|
Percentage
-------------------------------|------------------- Individual Coding Assignments |
70%
In-class Quizzes |
30% + 10% bonus
Your score will rely on the successful completion of the programming tasks, each described below. In-class micro-quizzes will test your knowledge of the more theoretical concepts. A detailed breakdown of each of these grading components follows. Coding Assignments **[**70%**]** ------------------------------------------------------------ We will provide 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: non-negotiable time-based penalty Failure to submit a (valid) assignment on time will result in time-based penalty: a -5% penalty per hour (rounded up to the nearest hour) will be applied to late submissions. Make as many myCourses submissions as you want before the deadline: we only grade the last (early) submission or the first late submission. We will not grant extensions. 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. Assignments deadlines are all at *11:59pm EST* on their respective due dates. ![Example A0 Output](http://www.cim.mcgill.ca/~derek/ecsex43/output_8_0.png width="32%") **Assignment 0 -- Python & Floating-point [0%]**
- Setup your Jupyter Notebook & Python environments - Explore floating point limitations on simple problems - *Estimated Work*: 1 -- 3 hours - "Due" at start of week #3 [January 20] - Assignment notebook available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A0.md.html) ![Image denoising from A1](https://adrien-gruson.com/research/2018_GradientCourse/img/teaser.jpg width="32%") **Assignment 1 -- Linear Least Squares [17.5%]**
- Forward and backward substitution - Cholesky factorization - Normal equations and polynomial fitting - Regularized image denoising - *Estimated Work*: 6 -- 12 hours - Due at start of week #6 [February 10] - Assignment notebook available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A1.md.html) ![Color segmentation from A2](http://www.cim.mcgill.ca/~derek/ecsex43/color_segmentation.png width="42%") **Assignment 2 -- Advanced Model Fitting [17.5%]**
- Polynomial regression - MLE, MAP - Expectation-maximization - Gaussian mixture models - Image color segmentation - *Estimated Work*: 6 -- 14 hours - Due at start of week #10 [March 9] - Assignment notebook available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A2.md.html) ![Depth of Field from A3](http://www.cim.mcgill.ca/~derek/ecsex43/DoF_natural.jpg width="34%") **Assignment 3 -- Convolution and Deconvolution [17.5%]**
- Spatially-varying image convolution - brute force - power iteration factorization - SVD for realistic kernels - Image deblurring with steepest descent - *Estimated Work*: 10 -- 15 hours - Due at start of week #15 [April 14] - Assignment notebook available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A3.md.html) ![Filtered Fourier Spectrum from A4](http://www.cim.mcgill.ca/~derek/ecsex43/output_41_0.png width="40%") **Assignment 4 -- FFT and Audio Processing [17.5%]**
- Discrete Fourier Transform - Brute force - Fast Fourier Transform - Analysing and Visualizing DFT Output - *Estimated Work*: 5 -- 12 hours - Due on the last day of the semester [May 1] - Assignment notebook available on [myCourses](https://mycourses2.mcgill.ca/) - Online handout available [here](http://www.cim.mcgill.ca/~derek/ecsex43/A4.md.html) !!! Tip For grading questions please contact the course grader: arbaaz.khan@mail.mcgill.ca In-class Micro-quizzes **[**30% + 10% bonus**]** ------------------------------------------------------------ An in-lecture quiz will be administered roughly every week, starting after the add/drop deadline. Each quiz will be worth 4% of your final score, and you can accrue up to 40% (i.e., we will not clamp your total to 30%). Extensions, Solutions and Absences ------------------------------------------------------------ We advocate strongly for students to begin assignments early and to review their corrected assignments in order to assess any errors they made. 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 non-negotiable, 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 Do not post solutions online. Refer to the [collaboration & plagiarism policies](#CollaborationPolicy) below. Course Topics & Schedule ===================================================================== The course combines slide-based lectures, hands-on tutorials, take-home programming assignments and in-lecture micro-quizzes. We will update the course schedule below as the semester progresses.
: 0a -- Introduction & Administration - Course administration - Course outline and schedule - Quiz, assignment and grading policies : 0b -- Floating Point - 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 : 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 : 1a -- Linear Algebra: Review - Review - 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) & (A1 out) - Gaussian elimination - forward/backward substitution - numerical issues - Elementary matrix operations and their inverses : 1b -- LU Factorization - Pivoting (partial vs. full) - LU performance - Solving systems with LU - Example #1: polynomial regression - Example #2: image deconvolution : 2a -- Linear Systems: Conditioning
Quiz #1 -- Linear algebra - 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
Quiz #2 -- LU & Cholesky - Review - Experiment, sample space, event - Discrete random variables - Probability mass function - Conditional probability : 3a -- Probability - Review - Total probability - Bayes' theorem - Continuous domain - Probability density function : 3b -- Maximum Likelihood Estimation - Explicit model of noise : 3b -- Maximum Likelihood Estimation
Quiz #3 -- Norms & Condition - 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
Quiz #4 -- QR & Regularization - 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
Quiz #5 -- MLE & MAP - Principal components analysis - Solving systems of ODEs : 4c -- Singular Value Decomposition : 4c -- Singular Value Decomposition : 4d -- SVD Applications
Quiz #6 -- Eigendecomposition (): Reading Week
(no class)
(A3 out) (): Reading Week
(no class) (): Reading Week
(no class) : 5a -- Root Finding
(A2 due) - Non-linear systems of equations - Bisection search - Convergence analysis : 5b -- Taylor Series & Convolution
(A3 out) - 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
Quiz #7 -- SVD - Higher-order root finding - Evaluating gradients - Secant method - Multivariable root finding - Vector calculus & Multivariable Taylor - Newton's method - Quasi-Newton methods : 5c -- 1D Optimization
Quiz #8 -- 1D Root-finding - 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 : 5e -- Gradient Descent
Quiz #9 -- Optimization - Basic gradient descent - Step size and count - Line search - Solving linear systems with gradient descent - Deriving the optimal step size - Motivating conjugate gradient (): Good Friday
(no class) (): Easter
(no class) : 6 - Fast Fourier Transform
Quiz #10 -- Gradient Descent
(A3 due) - Fourier Series & Transforms - Computing the DFT - Fast Fourier Transform - Applications : (A4 due) ():  
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). 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.