Let $A\in\mathbb R^{n,n}$. Consider the problem $Ax=b$ with some $b\in\mathbb R^n$. Which problem can be solved the fastest? $a)$ A is symmetric positive definite $b)$ A is a tridiagonal matrix $c)$ A is orthogonal
I am note sure if we can solve this problem the fastest if $A$ is symmetric positive definite with the procedure of conjugated gradient, but intuitively I would say that we can solve the problem really fast, if A is tridiagonal, but I do not know any better than $LU$ decomposition and if $A$ is orthogonal this problem will be solved the slowest, I guess.
Some enlightenment is welcome!
P.S. Or are there even some other special kind of matrices which can be solved even faster?
I think tridiagonal systems can be solved in linear time, whereas all others require at least a quadratic time to parse through the input. It's hard to beat linear time with quadratic input :)