1
$\begingroup$

Suppose we have a matrix $A$ of dimension $n \times n$ and two vectors $\vec{u}$ and $\vec{v}$ of dimension $n$.

Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(n)$ with the naive algorithm (since the output is a vector of length $n$).

(Forgive me if there is a better runtime. I don't know the current status of vector matrix multiplication.)

If we were to apply the dot product to our equation, we get $A\vec{v} \cdot \vec{u} = \vec{x} \cdot \vec{u}$. We know the final space complexity goes down to $O(1)$ for the result and $O(1)$ space complexity during the running time of the naive algorithm. But the naive algorithm is still $O(n^2)$ in time complexity.

Is there a way to manipulate the equation so that we get an improved time complexity without hurting the space complexity using the dot product?

A bonus question for pondering: Can we use operations that reduce information like the dot product (or for example other information destroying operations like the derivative) to speed up both the space and time of algorithms?

$\endgroup$
1
  • $\begingroup$ I'm fairly sure you can precompute something like $A \cdot \vec{u}$ - a $n \times 1$ matrix - and have $(A \cdot \vec{u})\vec{v} = (A\vec{v}) \cdot \vec{u}$. Something along those lines. I might have used the wrong notation and mixed up rows and columns. $\endgroup$ Nov 9, 2022 at 18:32

2 Answers 2

3
$\begingroup$

No. It is not possible to reduce the time complexity below $O(n^2)$ time. It takes $\Theta(n^2)$ time just to read every entry in $A$. Moreover, the result depends on every entry of $A$ (if there is any entry that the algorithm doesn't read, then the algorithm will produce the wrong output on some inputs). Consequently, every correct algorithm requires at least $\Omega(n^2)$ time to compute the answer.

So, the naive algorithm is asymptotically optimal.

$\endgroup$
1
$\begingroup$

If you expand your expression, the result is a linear combination of the terms of the outer product of $\vec u$ and $\vec v$, where the coefficients are the elements of $A$. So all these terms are independent and must all be evaluated.

A similar reasoning shows that the matrix/vector also has $\Omega(n^2)$ complexity (knowing the product does not allow you to reconstruct the matrix). The case of matrix/matrix is different, as the elements of the result are not independent (knowing the product and one matrix allows you to retrieve the other).


For the second part of the question, ponder this: armies of top-level mathematicians have been working hard on linear algebra problems for decades. All the useful techniques and algorithms are found in textbooks and taught at school. This is stable.

$\endgroup$
2
  • 2
    $\begingroup$ All the useful techniques and algorithms are found in textbooks and taught at school. As someone who is active in research in linear algebra, let me disagree. :) Some extremely useful novel techniques like randomized linear algebra have emerged just recently. Trace estimators like the one mentioned here are an active research topic useful in similar settings (computing $v^T A^{-1} v$). And ultimately even Strassen's algorithm for matrix multiplication was discovered only after mathematicians had been working on linear algebra for decades. $\endgroup$ Nov 9, 2022 at 17:33
  • $\begingroup$ @FedericoPoloni: these are the exceptions that confirm the rule. We can talk about Duan, Wu & Zhou if you want. arxiv.org/abs/2210.10173 $\endgroup$
    – user16034
    Nov 10, 2022 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.