1
$\begingroup$

Say $A$ is a $n\times n$ ($n$ odd) real matrix that is tridiagonal (but need not be symmetric). What is the most efficient way to compute the value of $x(\frac{n+1}{2})$ (informally, the 'middle value') where $Ax=b$? No assumptions are made on $b$. I am already familiar with tridiagonal solvers, so the part of the problem to focus on is obtaining the necessary values of $x$.

So far my code uses $x=A\backslash b$ and then just grabs the needed value, which is pretty fast in MATLAB. However, I feel like there might be a really nice trick here.

BONUS:
The thing I REALLY want is the answer for when $A$ is 'block tridiagonal' with block sizes $m$ and I want the middle $m$ values of $x$. ie. in MATLAB speak if $A$ was $3m\times 3m$ I want $x((m+1):2m)$

$\endgroup$
3
$\begingroup$

What you looking for is a Thomas algorithm which is a simplified form of a Gaussian Elimination or if you want LU decomposition.

Matlab looks fast because Matlab identifying such special cases and call in such case to a very effective solver for banded-matrices. This solver is little bit more general then Thomas algorithm. The very rough idea is that you know that you don't need to run over all matrix entries but only from the rightest to the leftest diagonal entry in each row.

Edit: to asnwer the added "BONUS" question

In order to retrieve specific entry of the x=A\b, given that only $\Theta(1)$ such values are required one could think about a Cramer's rule. However, using this method would be inefficient, since one need to compute at least $2$ determinants, which is briefly $O(n^3)$ operations. For a tridiagonal matrix one could find a determinant very fast, at only $O(n)$, see here.

However, you talking about retrieving $m=O(n=3m)$ values, which by Cramer's rule would mean $m+1$ determinants, so $O(mn)$. Thus, using Thomas algorithm is much more efficient, since it require $O(n)$ computational steps only.

Note that your problem cannot be solved faster then $O(n)$ since you have $m=O(n)$ unknowns. In the best situation you could improve a constant hidden under the sign of $O$ which isn't too big ($\approx 9m$?).

http://www.sciencedirect.com/science/article/pii/S0377042703007726

$\endgroup$
  • $\begingroup$ This is nice, but doesn't help us obtain particular values of $x$. $\endgroup$ – InfiniteElementMethod Nov 25 '15 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.