A fast algorithm for solving systems of linear equations with two variables per equation

Abstract

We present a fast algorithm for solving m X n systems of linear equations A x = c with at most two variables per equation. The algorithm makes use of a linear-time algorithm for constructing a spanning forest of an undirected graph, and it requires 5m + 2n - 2 arithmetic operations in the worst case. © 1980.