csc148			Some remarks about the efficiency of
Spring 1996		Cholesky Factorization
===============================================================================

In the sample solution, there are two procedures which perform the
symbolic Cholesky factorization. This purpose of this note is to 
explain the difference.

If you trace through the procedure given to you on page 9 of the
handout, you should notice that it creates the output matrix L one
column at a time. The procedure "symbolicCholeskyCol" matches this
code very closely. 

In the computation of L(i,j), the Cholesky factorization routine
only uses values of L which are both to the left of L(i,j) and
also above it. This means that there is no particular reason why 
we have to process columns rather than rows. "symbolicCholeskyRow"
is a version of Cholesky factorization which computes L by rows.
This looks a little bit more complicated but there is a slight advantage
which is evident when one analyzes the complexity of the two
procedures.

Column-wise version:
    - Values are only added to the end of rows so this is always done in O(1).
    - O(n^2) values are added.
    - doIntersect() takes time O(n).
    - doIntersect() is called for every zero element of M.
    - value() takes O(n) time.
    - value() is called n^2 times.

    - Complexity = O(n^3 + z*n) where z = # of zero elements of M.

    - Since z <= n^2, the complexity is O(n^3).

Row-wise version:
    - Values are only added to the end of rows so this is always done in O(1).
    - O(n^2) are added.
    - doIntersect() takes time O(n).
    - doIntersect() is called for every zero element of M.

    - Complexity = O(n^2 + z*n) where z = # of zero elements of M.

    - Since z <= n^2, the complexity is O(n^3)

Even though the asymptotic complexity of both versions is the same,
you should notice that if there are many zero elements (M is sparse), z
will be much less than n^2. In this instance, the row-wise version
will have asymptotic behaviour of strictly less than O(n^3) while
the column-wise version will still have O(n^3) complexity.

This difference stems entirely from our choice of data structure. We
chose to store the matrix as a collection of rows. This makes scanning
a row more efficient than scanning a column. If we had chosen to
implement a matrix as a collection of columns, the opposite would be
true.