School of Computer Science (SCS) researchers have made advancements in algorithms for solving structured systems of linear equations. This result, Incomplete Nested Dissection, was presented at the 50th ACM Symposium on Theory of Computing (STOC 2018) in Los Angeles from June 25–29.

SCS Assistant Professor Richard Peng, Ph.D. student Peng Zhang, master’s student Robert Schwieterman, and Yale alumnus Rasmus Kyng developed a faster algorithm for geometric 3-D truss linear equations, which is the first improvement for this class of problems since 1990.

It follows a previous result by Kyng and Zhang that showed, among other results, that general 3-D trusses are difficult to solve. That paper, Hardness Results for Structured Linear Systems, won the Machtey Prize for best student paper at the 58th Annual IEEE Symposium on Foundations of Computer Science in Berkeley in October 2017.

Solving linear equations is a central tool in statistics, machine learning, optimization, and engineering. However, since algorithms for solving general systems of linear equations are slow, practitioners use additional geometric structure in their problems to get significantly faster linear equation solvers for important cases like finite element simulation used for collision modeling.

One important development in this research is the creation of provably correct and fast algorithms for classes of structured linear equations related to heat diffusion and logistics problems in networks for spectral methods and semi-supervised learning on graphs. These are the most important and well-studied systems of equations, and the algorithm provably runs in time close to input size.

 This gives researchers hope that other structured linear equations in other fields/disciplines? could also be solved quickly by provably correct methods.

Speeding up truss equation solvers by geometric methods

One representative class of structured linear equations is truss matrices. They model connections between objects as ideal rods (a notional rod in physics that has no weight, mass, or damping loss). Truss matrices also illustrate the difficulty of designing better algorithms that work for any structured input; work on designing provably efficient algorithms for trusses has been ongoing for almost three decades.

The new algorithm for geometric 3-D trusses combines two methods that are workhorses of scientific computing: the conjugate gradient (CG) algorithm and nested dissection.

CG solves the overall linear system by repeatedly solving similar, but easier systems. Nested dissection, on the other hand, uses the underlying geometry to partition the problem. The team combines these two algorithms, leading to an algorithm that hollows out geometrically local pieces of the trusses (as in the diagram below).

“While this small improvement is mostly of theoretical value,” Kyng said, “the directions offered by it are quite exciting. We can now quantify how much geometry helps in scientific computing, and some of the geometrically motivated ideas may extend to more general systems.”

Not all structures help

The new algorithm for geometric 3-D trusses comes on the heels of a recent negative result by Zhang and Kyng. In their paper, Hardness Results for Structured Linear Systems, Zhang and Kyng demonstrated that many linear systems with specialized structures, including general 3-D trusses, are not significantly simpler than general systems.

They demonstrated that any system of linear equations can be written as one with truss structure in 3-D. This gives a reduction, meaning if a better algorithm is found for solving trusses, it would immediately give a better algorithm for solving any system of linear equations. Consequently, general 3-D truss equations without geometric structures are as hard to solve as arbitrary linear equations.

“Before this hardness result, there was optimism that most classes of practically relevant systems can be solved faster,” said Peng. “The necessity of geometric structures in faster algorithms is surprising to many in the area, but also validates what scientific computing has long believed.”