Geodesic
Solving systems of linear equations with quasi-Toeplitz coefficient matrices
Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XXV, Tome 405 (2012), pp. 127-132 
Kh. D. Ikramov. Solving systems of linear equations with quasi-Toeplitz coefficient matrices. Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XXV, Tome 405 (2012), pp. 127-132. http://geodesic.mathdoc.fr/item/ZNSL_2012_405_a9/
@article{ZNSL_2012_405_a9,
     author = {Kh. D. Ikramov},
     title = {Solving systems of linear equations with {quasi-Toeplitz} coefficient matrices},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {127--132},
     year = {2012},
     volume = {405},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_405_a9/}
}
TY  - JOUR
AU  - Kh. D. Ikramov
TI  - Solving systems of linear equations with quasi-Toeplitz coefficient matrices
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 127
EP  - 132
VL  - 405
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_405_a9/
LA  - ru
ID  - ZNSL_2012_405_a9
ER  - 
%0 Journal Article
%A Kh. D. Ikramov
%T Solving systems of linear equations with quasi-Toeplitz coefficient matrices
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 127-132
%V 405
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_405_a9/
%G ru
%F ZNSL_2012_405_a9

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

A matrix $A$ is said to be quasi-Toeplitz if its entries in positions $(i,j)$, $(i-1,j)$, $(i,j-1)$, and $(i-1,j-1)$ obey a linear relation with coefficients that are independent of $i$ and $j$. It is shown that a system of linear equations with a quasi-Toeplitz $n\times n$ coefficient matrix can be solved in $O(n^2)$ arithmetic operations.

[1] G.-S. Cheon, S.-G. Hwang, S.-H. Rim, S.-Z. Song, “Matrices determined by a linear recurrence relation among entries”, Linear Algebra Appl., 373 (2003), 89–99 | DOI | MR | Zbl

[2] T. Mingshu, “Matrices associated to biindexed linear recurrence relations”, Ars. Comb., 86 (2008), 305–319 | MR | Zbl