Marching Algorithms for Elliptic Boundary Value Problems. I: The Constant Coefficient Case

Several new fast direct methods for solving constant coefficient elliptic boundary value problems are presented. The methods make extensive use of the algebraic properties of the modified Chebyshev polynomials Sₙ (x) and Cₙ (x), which allow us to obtain operation counts of O(n² ) or O(n² log ₂ (n / k)) for solving problems on an n × n grid. The algorithms are shown to be numerically stable by giving a Wilkinson-style error analysis. Previously studied fast direct methods, and shooting and multiple shooting techniques are related to the algorithms.