Solving a linear system with a block Toeplitz matrix

Hi. I have a line of code that looks like x=b\A; where A is an NxN block Toeplitz matrix and b is Nxm.

I don't know whether Matlab automatically recognizes A as block Toeplitz and optimizes the solver accordingly. Is there any way to tell? Is there an easy way to tell Matlab to use a routine for block Toeplitz matrices?

Answer 1

[Robert]

Figured it out: http://www.mathworks.com/matlabcentral/fileexchange/30931-block-levinson-solver

Answer 2

[Feruza Amirkulova]

Hi!

For a complex valued non-Hermitian matrix Block-Toeplitz matrix of level one you may use TOEPLITZ FORTRAN solver available at: http://people.sc.fsu.edu/~jburkardt/f_src/toeplitz/toeplitz.html

Algorithms are given in book by V.V. Voevodin, E.E. Tyrtyshnikov, Numerical Processes with Toeplitz Matrices, Nauka, Moscow, 1987 (in Russian). I first used algorithms in MATLAB, and wrote codes for examples from the book. There is no translation of the book, but you my get an idea on algorithms looking at our JCP paper published in 2015, "Acoustic multiple scattering using recursive algorithms" (you may google it to find it online). You may find additional info from User's Guide: Oleg Arushanian, MK Samarin, Valentin Voevodin, Evgeny Tyrtyshnikov, Burton Garbow, James Boyle, Wayne Cowell, Kenneth Dritz, The TOEPLITZ Package User's Guide, Argonne National Laboratory, ANL-83-16, 1983. I used these algorithms for solving a linear system of equations of level one Block Toeplitz structure for acoustic multiple scattering problem. I used this algorithms first in my laptop using MATLAB, then on HPC clusters in parallel using TOEPLITZ solver; TOEPLITZ solver is fast and works even when LAPACK solver stops working due memory limitations. The method is exact, it is not an approximation. It was not that hard to transfer my Matlab codes to Fortran 90. If you need I may still find (I need to dig in hard-drive) simple Matlab codes for examples from Voevodin's and E.E. Tyrtyshnikov's books.