CS20c Progress Report
by
Tasha Vanesian
Joy Qiu
Title: Exploration of Structured Matrix Computations
Introduction
The purpose of this project is to understand matrix computations as performed by
computer algorithms. Because of the irregularities of a random matrix, we are dealing
only with well structured matrices of the type Toeplitz, Hankel, Vandermonde, and Cauchy.
Victor Y. Pan proposed an algorithm which uses O((nlog2n)log log n)
operations to compute the rank and basis for the null space of a structured matrix. The
algorithm can also solve a linear system Xy=b or determine its inconsistency, as well as
compute the determinant and inverse of an n x n matrix of rank n.
Current Status
We understand the different types of well structured matrices mentioned in the paper. We
have worked through most of the math for the divide and conquer algorithm for general
matrices and have learned about the Schur complement of X11 in X where
We have written code which partitions an n x n matrix into 4 submatrices and vice versa. We have also implemented code that does matrix operations like multiplication, addition and subtraction.
For further description of the algorithm, please view our code .
We had difficulty understanding the mathematical notation used in the algorithm which
computes the complete recursive factorization (CRF) and the inverse of a matrix X.
We think we have an understanding of it now, which will help us to interpret the rest
of the paper.
Implementation of algorithms is difficult in Lisp because representation of matrices
is challenging with the available constructs. Despite this difficulty, we still think
Lisp is a good language to use because of the use of recursion in the algorithms.
Major Milestones
1. We have understood most of the mathematical derivations in the paper.
2. We have found references which are useful for our understanding (see below).
3. We understand the matrices which are considered "well structured" and thus
valid for the paper.
4. We have begun implementation of a divide and conquer algorithm.
5. We will compute the rank of a matrix.
6. We will compute the inverse of a matrix.
7. We will prepare a presentation for the class.
Items which will probably be included in the presentation:
A discussion of well-structured matrices
A short description of algorithms we implement
Milestones which have changed:
We will do the following only if we have time:
basis for the null space
a solution to a linear system
if the matrix is nonsingular, output the determinant
References
D. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 1:
Fundamental Algorithms , Birkhauser, Boston, 1994.
Victor Y. Pan, Nearly Optimal Computations With Structured Matrices,
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms ,
San Francisco, CA (2000).
V.Y. Pan, A Unified Superfast Divide-and-Conquer Algorithm for Structured Matrices,
MSRI Preprint 1999-033, Mathematical Sciences Research Institute ,
Berkeley, California (1999).
Also, we found a web site which gives easy to understand explanations of the different
types of structured matrices presented in the paper.
www.omatrix.com
E-mail Joy and Tasha!
Last updated: 5-24-01