Patent ID: 6694343
Filing Date: 2004-02-17
Classification: G06F

Abstract:
A computer-based method of solving a sparse triangular system of linear equations Ax=b, said method comprising:retaining in computer storage an ordered data structure containing indices of all non-zero values of said vector x; compiling a contiguous list v of all non-zero values of said vector x; identifying a vector p of pointers that point to the non-zero values of said vector x in said list v; reading said vector b; identifying all non-zero entries in said vector b; placing all non-zero indices of b in said ordered data structure; reading the index at the top of said ordered data structure; deleting said read index from said ordered data structure; returning to said step of reading the index at the top of said ordered data structure if said index already exists in said vector p, else reading a column of said vector A corresponding to said read index if said index does not already exist in said vector p; calculating a value x from said read column of said vector A; updating v and p based on said calculated value of x; returning to said earlier step of reading said index at the top of said ordered data structure if said ordered data structure is not empty, and ending computations if said ordered data structure is empty.