A linear complexity algorithm to solve large sparse linear systems

Many physical systems can be modeled using linear relations, and some direct methods to solve linear algebraic equation systems have an O(n 3 ) complexity. Optimized versions of faster solutions for sparse symmetric banded systems handle the data through the skyline schema. This paper comments a way to organize the data and the algorithm structure to solve sparse diagonal dominant linear systems in linear time. The advantage of the present proposal is that the values distinct from zero do not have to be in a band close to the main diagonal. The solution is fast enough to solve a system with 25 non-zero entries per row, 64,000 equations, in 21.3 seconds, with a precision of 10 –12 .