\(\mathcal O(n)\) working precision inverses for symmetric tridiagonal Toeplitz matrices with \(\mathcal O(1)\) floating point calculations (Q1744639)

The paper deals with the inversion of large symmetric tridiagonal Toeplitz matrices of size \(n \times n\), that is, matrices whose entries equal \(a\) on the main diagonal and \(b\) on the extra diagonal, where \(a\) and \(b\) are real numbers. It is known that the inverses of such matrices are dense and there exist explicit formulas by which they can be calculated in \(O(n^2)\). However, for \(n \geq 10^5\) this quadratic complexity is too costly. In this paper, the author derives a simplified inversion formula if \(|a|>2|b|\), that is, the matrix is, in addition, strictly diagonally dominant. In this case, its inverse is a band matrix to working precision and the bandwidth is independent of \(n\) for sufficiently large \(n\). Then, the author uses this simplified form to devise a Matlab style pseudocode for an explicit inversion with \(O(n)\) read-write operations and integer additions (in the form of running indices) that uses only \(O(1)\) floating point operations. Finally, this simplified inverse structure is used to outline an approximative equation solver that runs in roughly \(4n\) fused multiply-adds and is communication free and thus parallelizable in a straightforward fashion.