Skip navigation

Solving Linear System of Equations

  • Solving Linear System of Equations Using Computer Graph Theory

    Solving SDD systems has always been an interesting topic in computational mathematics. When the matrix is sparse, one would expect the algorithm to run efficiently with respect to the amount of nonzero entries. Spielman and Teng developed an SDD solver (ST solver) that runs in nearly linear time. The idea of spectral sparsification and its use in matrix reduction was proposed in their work. 

    The ST solver solves the SDD system iteratively by the classic Preconditioned Conjugate Gradient method or the Preconditioned Chebyshev Method. The preconditioners are constructed using spectral sparsification in graph theory, which are reduced into smaller size systems by some direct method.

    Researchers from CMU recently improved the ST solver by varying the process of sparsification and greatly enhanced the algorithm efficiency.

    In our research, we implemented the algorithm by Matlab. Experiments on different types of SDD systems are be conducted to test the robustness and feasibility of the algorithm. The program is applied to example heat dynamic differential equations and other real problems. The numerical results will be compared with results obtained from other algorithms.  

    Applied Math Figure 1Applied Math Matrix Figure 1

    Figure 1: A graph with its adjacency matrix

    Applied Math Figure 2

    Figure 2: Sparsifying a dense graph