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.
4
$\begingroup$
$\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$
$\endgroup$
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.
3
$\begingroup$
$\endgroup$
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.
