Solving certain symmetric positive definite linear equations by constructing provably good cheap preconditioners

Professor Vaidya and his team will study the system of linear equations Ax=b  where A∈R ^n×n  is a symmetric positive definite diagonally dominant (SPDDD) matrix. They give an algorithm that computes an ϵ-approximate solution based on utilizing certain combinatorial properties of a weighted undirected graph G(A) associated with A in order to construct a good preconditioner for A. This technique for constructing preconditioners leads to even better algorithms for solving Ax=b  if G(A) has a special structure which is the case in many practical applications. Professor Vaidya intends to implement this method for constructing preconditioners and the associated algorithms for solving linear equations, and to test them on several practical problems. They will also investigate how to extend these ideas to matrices that arise in finite element applications, and to asymmetric matrices whose symmetric part is diagonally dominant and whose asymmetric part is not too large. Such matrices are structurally similar to SPDDD matrices.