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.

  • 2
    $\begingroup$ If it would be for an abstract, I would choose the wording of your title. $\endgroup$ – Dirk Oct 2 '18 at 19:35

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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