Let's say we want to solve for the eigen-values of a symmetric matrix of size $n$ x $n$.
In the Phase 1 of the computation, the matrix is reduced to a tridigonal form using Householder/Arnoldi's reduction.The theory says that this is $O(n^3)$.
In the Phase 2 of the computation, this tridigonal form is transformed to a diagonal form by using the Normalized Simultaneous Iteration (NSI). The two main steps in this iteraion are matrix multiplication of tridigonal matrices and the qr factorization of a tridigonal matrix. Each of these (if implemented specially for tridigonal systems) will be $O(n)$. Since these are to be repeated $n$ times, the total would be $O(n^2)$.
I want to see experimentally that the phase 1 actually reduces the time for computation. The easist way to do this is in MATLAB which uses the DGEMM routine for matrix multiplication and Householder reflector for qr factorization.
My question is : Does the qr algorithm and the DGEMM used in MATLAB take into account if the input matrix is tridigonal and optimize accordingly ? The documentation says that it differentiates between sparse and dense matrices.
If I have to write a code separately for matrix multiplication of tridigonal systems and a qr using householder reflector, will it be better than the ones provided in MATLAB ?
Is there a way to do this using something other than MATLAB , like a C or C++ library ?