Project Title: Exploration of Structured Matrix Computations

1st choice:

Description

This paper suggests an algorithm that analyzes well-structured matrices of the types Toeplitz, Hankel, Vandermonde, and Cauchy. In order to implement this algorithm Pan refered to other algorithms including "divide and conquer" and FFT. His algorithm not only allows one to determine the rank and a basis for the null space of the matrices mentioned, but also solves the linear system Xa = b, where X is the well-structured matrix. The algorithm also suggests methods for other computations.

In doing this project we need to recognize the types of matrices that are considered "well-structured" enough for the algorithm to work, and understand the mathmatical proofs and derivations. We will also face the challenge of fully understanding the "divide and conquer" method and other algorithms in order to implement our project. The project has already been approved by Professor Arvo. Our ideas will implemented in LISP.

Major Milestones

1. Understand the mathematical proofs and derivations in the paper.
2. Find cited references which would be useful in understanding the paper.
3. Determine for which types of matrices the algorithm proposed by the paper is valid.
4. Determine which parts of the algorithms we will implement.
5. Implement at least one of the following algorithms (more if time permits):
   • computing the rank
   • basis for the null space
   • a solution to a linear system
   • If the matrix is nonsingular, output the determinant
6. Improve algorithm to be more optimal, if time allows.
7. Prepare a presentation for the class.

Participants

2nd choice:

Last updated: 5-8-01