Introduction
Matrix numerical analysis is the analysis of numerical algorithms for solving matrix problems,
and is also known as numerical linear algebra. While at first sight the problem:
Given a vector b and an nxn matrix A, find x such that Ax=b
may not sound very exciting, much of the modern world has a computer element,
and since computers are particularly adept at storing vectors and matrices, nearly
any problem expressed as a computer algorithm eventually reduces to Ax=b
or one of its generalisations, in particular eigenvalue problems Ax=λx.
Perhaps the most famous eigenvalue problem is the problem of PageRank at the heart
of the google search algorithm. In this case x is the vector of pageranks
of all the pages on the web, and A is the connectivity
matrix for the internet. Thus x has about 25x109 entries
and A will be a 25x109 by 25x109 matrix
with about 6.25x1020 entries. Gaussian elimination would require about
1030 operations to invert the matrix and solve the problem. In theory, some of the fastest
supercomputers in the world could complete this computation in less time than the current
age of the universe. In practice, there will be new webpages on the internet tomorrow, and so
tomorrow's PageRank will be different to today's, and we will want to update the PageRank in realtime.
This is a difficult problem, which has so far earned Larry Page about $20billion. Now does
Ax=b sound more interesting?
Matrix numerical analysis is also central to many other fields including signal and image processing, (how do they mange to squeeze so many high definition tv channels down one cable to your tv?) bioinformatics, data mining, as well as the more obvious fluid dynamics, materials science and the numerate sciences.
This is an introductory course matrix numerical analysis. We will consider the main basic problems, of linear systems including under and overdetermined problems, and eigenvalue problems and the main direct and iterative methods to solve them.
Derivation and analysis of the algorithms will be an essential part of the course. Does the algorithm give the exact answer? If not, is the error small, and in what sense?
We will also use matlab to implement some of these algorithms and experiment with others (most of them are already implemented in matlab) on the computer. If you have not used matlab before, you will need to be prepared to learn some.
The honours version of the course will share lectures with the majors version, but assignments, midterms and final exams will be different.
Syllabus
An overview of numerical methods for linear algebra applications and their analysis. Problem classes include linear systems, least squares problems and eigenvalue problems.
Topics
Audience/Prerequisites
The course is intended for all students with an interest in matrix numerical analysis. The class will combine theory and practice, with the emphasis towards theory. Nevertheless we will also use matlab to perform computations.
The prerequisites are
References:
You probably will not need to buy a book for this course.
I intend to use
Computing skills will be assumed in this course (COMP202 prereq). I will supply some matlab assistance and examples, but you will be largely expected to learn matlab yourselves. There are many good online guides that can be found using google. But, here are
My Courses
This class will be run using MyCourses and you will need to be registered to receive e-mail announcements, and to receive and submit assignments. This page is only intended to provide information to students considering registering and will not be updated after the course commences.
Further Information