A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices

作者：Poloni Federico^*

来源：Numerical Algorithms, 2010, 55(1): 115-139.

DOI：10.1007/s11075-010-9361-5

• Cauchy-like matrix
• GKO algorithm
• Displacement structure
• Structured linear system
• Toeplitz matrix

We propose a new O(n)-space implementation of the GKO-Cauchy algorithm for the solution of linear systems where the coefficient matrix is Cauchy-like. Moreover, this new algorithm makes a more efficient use of the processor cache memory; for matrices of size larger than n a parts per thousand 500-1,000, it outperforms the customary GKO algorithm. We present an applicative case of Cauchy-like matrices with non-reconstructible main diagonal. In this special instance, the O(n) space algorithms can be adapted nicely to provide an efficient implementation of basic linear algebra operations in terms of the low displacement-rank generators.

• 出版日期2010-9