I am wondering, which one is more expensive to compute (in terms of multiplications):
1). $\left(A^TDA + \mu I\right)^{-1} x$
2). $A^TDA y$,
where matrix $A \in \mathbb{R}^{n \times m}$, diagonal matrix $D \in \mathbb{R}^{n \times n}$, $x,y \in \mathbb{R}^{n \times 1}$, and $\mu$ is a scalar.
My take is that 1) is more expensive to compute than 2).
- The worst-case complexity of matrix-matrix product of $A^TDA$ is $O(m^2n)$. Correct?
- Worst-case complexity cost for 1) would be $O(m^2n + m^3 + m^2n)$, where $m^3$ is due to matrix inversion and $m^2n$ is due to matrix-vector product. Correct?
- Worst-case complexity cost for 2) would be $O(mn)$. [See comment from JimmyK4542]
- Further, one could also parallelise the matrix-matrix-vector product operations. However, the matrix inversion can not be parallelised. Agree?