On linear-time solvers for comrade linear systems (Q2332725)

This paper aims at solving a complex linear system of equations with a nonsingular comrade matrix. Two factorization based algorithms are introduced and their numerical stability is analyzed. Algorithm 1 (based on the \(UL\) factorization) outperforms previous methods for comrade systems in its speed, however it can be potentially unstable for large-order comrade linear systems. Algorithm 2 overcomes this problem by replacing the traditional \(LQ^\top\) factorization by a \(QR\) factorization of a matrix transpose. Even though Algorithm 2 has larger computational complexity than Algorithm 1, it is still quite efficient (linear-time solver). Numerical experiments support clearly the presented results.