Systolic algorithms providing near ideal speedups have been developed
for solving a dense system of linear equations. However, in applicatio
ns like circuit simulation, the resulting matrix equation is quite spa
rse( > 99% zeros) which makes the dense matrix solution approach ineff
icient. Although sparse matrix solvers for circuit simulation have bee
n devised for parallel shared memory machines and vector processors, t
heir performance in terms of speedup has been limited due to tightly c
oupled and unstructured sparse equations. This paper first develops a
systolic sparse matrix algorithm by modifying an existing partitionabl
e dense matrix solution algorithm. The sparse algorithm is then furthe
r improved to include parallel execution by multiple systolic processo
r modules. Reordering schemes based on a modified Markowitz algorithm
are also developed that minimize the fill-in-during the matrix solutio
n by our sparse algorithms thereby improving the execution time. Resul
ts on several randomly generated sparse matrices and those generated f
rom ISCAS benchmark circuits are presented to show the efficiency of o
ur sparse algorithm and its excellent speedup as the number of process
ors in the systolic array is increased.