4
$\begingroup$

Many dense linear algebra decompositions (QR, SVD...) on an $m\times n$ matrix have cost $$ O(\max(m,n)\min(m,n)^2) $$ when implemented in practice on a computer. Is there a colloquial name or a more compact notation for this complexity? For instance, something like "linearithmic"? Or, how would you write it in the most compact and understandable form? Think about writing it in an abstract, for instance.

$\endgroup$
  • 3
    $\begingroup$ If it would be for an abstract, I would choose the wording of your title. $\endgroup$ – Dirk Oct 2 '18 at 19:35
  • $\begingroup$ I revise my above comment in view of my answer below! "Big-times-small-squared complexity" seems better. $\endgroup$ – Dirk Feb 1 at 9:50
3
$\begingroup$

The book "Introduction to Applied Linear Algebra" by Boyd and Vandenberghe has an appendix about complexity of basic operations in linear algebra and the call this case

big-times-small-squared complexity.

enter image description here

$\endgroup$
3
$\begingroup$

Many authors avoid the problem entirely using the terms "tall and skinny" matrix, as in following example:

"Let $m \gg n$ and let $A \in \mathbb{R}^{m \times n}$ be a tall and skinny matrix. The QR decomposition of $A = QR$ (where $R \in \mathbb{R}^{n \times n}$) can be computed using $O(mn^2)$ arithmetic operations ..."

Given the assumption of $m \gg n$, is not strictly necessary to invoke the phrase "tall and skinny", but there is no harm done and it enforces the message we are trying to convey. Let us continue with an SVD:

" ... Now given $A = QR$ we can compute the SVD of $R = U \Sigma V^T$ using at most $O(n^3)$ arithmetic operations. We arrive at $A = (QU)\Sigma V^T$, the SVD of the matrix $A$.

I am not aware of any specialized term which covers your precise situation. It would not be wrong to write something along the lines of

"The flop count is $O(pq^2)$, where $p=\max\{m,n\}$ and $q=\min\{m,n\}$."

but this is not quite as illustrative as the above. I would hesitate to invent new terms unless absolutely necessary.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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