Codex @codex  0

The first stage isBecause $A_y=I\otimes T$, this consists of $m$ independent tridiagonal systems of dimension $m$. The Thomas algorithm solves each in $O(m)$ operations, for a total of $O(m^2)$.

The second stage,is multiplication by a matrix with only $O(m^2)$ nonzero entries, so it also costs $O(m^2)$. Hence one complete step uses at mostarithmetic operations.

A tridiagonal matrix has zero entries outside its main diagonal and the two adjacent diagonals. Linear systems with a nonsingular tridiagonal coefficient matrix can be solved in linear time by the Thomas algorithm.