I have two questions that I want to ask. Consider the following system:
$$BM = A$$
i) $B$ is a $n$ by $n$ tridiagonal matrix and $A$ is a diagonal matrix. What is the leading order computation cost for calculating $M$.
ii) $B$ is $n$ by $n$ full matrix and $A$ is diagonal. What is the cost in this case?
The way I have thought:
i) If we think of Thomas algorithm then it costs ~$8n$ flops to solve for a linear system of the form $Bx=c$. So if I am thinking of $n$ by $n$ matrix then it will go as ~$8n^2$. However this does not take into account that $A$ is diagonal.
ii) Same for this case. How to determine the flops if $A$ is diagonal.
Thanks in advance.
(Note: I know that there have been developments in matrix computation and there are better algorithms to solve systems without elimination. However I am specifically interested to find the cost in context of elimination process).
Let $M=[m_{i,j}],A=diag(A_i)$. If $B$ is invertible, then let $B^{-1}=[b'_{i,j}]$.
Using $n$ times the Thomas' algorithm, we obtain $B^{-1}$; the associated complexity is $6n^2$ mult.-divis. (denoted MD); note that $B^{-1}$ is a full matrix. Finally, the formulae $m_{i,j}=b'_{i,j}a_j$ give $M$ with $n^2$ supplementary mult.. The total complexity is $7n^2$ MD for the calculation of $M$.
If $B$ is full, then the complexity of the calculation of $B^{-1}$ is $n^3$ MD and it is also the total complexity.
EDIT. We can do better for 1. Let $M=[M_1,\cdots,M_n],A=[A_1,\cdots,A_n]$; it suffices to solve the $n$ equations $BM_i=A_i$.
STEP 1. By Thomas, we calculate the LU decomposition of $B$ (cost: $2n$ MD).
STEP 2. We use $n$ forward-backward with a cost of $3n$ MD each. The total cost is $\sim 3n^2$ MD.
Note that we do not use the fact that $A$ is diagonal.