If I have a fixed (known, unchangable) matrix $A$ of dimension $n\times n$, and a random vector $x$ of dimension $n$, is it possible to calculate the $Ax$ and/or $x^HAx$ with complexity less than $O(n^2)$ with some pre-computed intermediate results?
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
6 I think that the calculation of $Ax$ needs at least $\sim n^2$ complex multiplications ($\times$).
For $x^*Ax$, I assume that $A$ is hermitian and that we calculated its Gauss decomposition in squares.
EDIT 1. That follows is a reference in french language https://fr.wikipedia.org/wiki/R%C3%A9duction_de_Gauss
EDIT 2. The Gauss decomposition does not need the calculation of the eigenvalues. This decomposition is essentially in the following triangular form: $x^*Ax=\sum_i \pm|\sum_{j\geq i}u_{ij}x_j|^2$. Then the calculation of a certain $y^*Ay$ needs $\sim n^2/2$ $\times$.
- $\begingroup$ Would you please do me a favor to point out any reference I can found of 'the Gauss decomposition in squares'? Thanks a lot! $\endgroup$george andrew– george andrew2016-02-18 03:06:21 +00:00Commented Feb 18, 2016 at 3:06
- $\begingroup$ Hi loup blanc, thanks for your reply. Would you please explain more about how you get the triangular form: $x^*Ax=\sum_i \pm|\sum_{j\geq i}u_{ij}x_j|^2$? I think time reduction of factor of 2 is also good. The reference seems only talking about the eigen-decomposition. $\endgroup$george andrew– george andrew2016-02-20 15:05:21 +00:00Commented Feb 20, 2016 at 15:05
- $\begingroup$ @ george andrew , if you are interested by my post, then upvote it. $\endgroup$user91684– user916842016-02-20 20:05:50 +00:00Commented Feb 20, 2016 at 20:05
- $\begingroup$ Thanks loup blanc, I am sorry I am not very familiar with the system. I've just voted for the answer, but didn't see score change FYI. $\endgroup$george andrew– george andrew2016-02-21 00:48:43 +00:00Commented Feb 21, 2016 at 0:48
- $\begingroup$ @ george andrew , upvoting requires at least 15 points. Have a look on my edit. $\endgroup$user91684– user916842016-02-22 12:08:25 +00:00Commented Feb 22, 2016 at 12:08