An Overview Of Approximate Linear Complexity Algorithm For Symmetric Diagonally Dominant Linear Equations

Solving linear equations is an important part of numerical linear algebra,which is widely used in various fields.Particularly,symmetric diagonally dominant linear equations are widely used in the theoretical and practical calculations of computer science.In recent years,theorists from computer science have proposed two types of nearly linear time algorithms and their improvements for solving symmetric diagonally dominant linear equations.The thesis summarizes the nearly linear time algorithm based on circulation update proposed by Kelner,Orecchia,Sidford and Zhu from the perspective of optimization.The necessary proofs as well as the related explanations are added,and the relationship between the algorithm and the random coordinate descent methods in optimization is established.Numerically,the thesis reviews the currently only existing nearly linear time algorithm implementation.Explanations of the numerical performance are disscused using optimization theory.Up to now,advances in basic graph theory problems,graph theory algorithm,etc.derived from the symmetric diagonally dominant linear equations all stem from the complexity conclusion of nearly linear time algorithm.This thesis summarizes the theory and implementation of nearly linear time algorithm for solving symmetric diagonally dominant linear equations,which lays a solid foundation for using the idea of ??nearly linear time algorithm to break longstanding barriers in the basic graph theory problem,graph theory algorithm and practical application.