= Tridiagonal solve costs
{title2=$8n-7$}
For the displayed unpivoted <Thomas algorithm> with one right-hand side, count each scalar <addition>, <subtraction>, <multiplication> or <division> as one <arithmetic operation>. Forming $m_i,p_i,g_i$ takes five <arithmetic operations> per forward step. The last unknown takes one <division>; each remaining <back substitution> step takes three <arithmetic operations>. Thus
$$
5(n-1)+1+3(n-1)=8n-7.
$$
This is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original <tridiagonal matrix> needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total <space complexity>.
For repeated right-hand sides, retain the <LU decomposition>: computing $m_i,p_i$ once costs $3(n-1)$ <arithmetic operations>, and each subsequent pair of <forward substitution> and <back substitution> sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ <arithmetic operations>. This is the banded counterpart of <Reusing LU factors for multiple right-hand sides>.
Back to article page
