计算科学 - 线性代数的典型“较大维度中的线性，较小维度中的二次”成本的术语 - 吾爱随笔录

计算科学线性代数参考请求矩阵分解

2021-12-20 23:57:57

矩阵上的许多密集线性代数分解（QR、SVD...）在实现时花费在电脑上练习。这种复杂性是否有通俗的名称或更紧凑的符号？例如，像“linearithmic”这样的东西？或者，您将如何以最紧凑和易于理解的形式编写它？例如，考虑将其写成摘要。 $m\times n$

O (max (m, n) min (m, n)^{2})

$O(\max(m,n)\min(m,n)^2)$

2个回答

Boyd 和 Vandenberghe 的《应用线性代数导论》一书有一个关于线性代数中基本运算复杂性的附录，他们称这种情况为

许多作者使用术语“又高又瘦”的矩阵完全避免了这个问题，如下例所示：

"令和是一个又高又瘦的矩阵。的 QR 分解（其中 ) 可以使用算术运算来计算 ..." $m \gg n$ $A \in \mathbb{R}^{m \times n}$ $A = QR$ $R \in \mathbb{R}^{n \times n}$ $O(mn^2)$

鉴于的假设，调用短语“tall and skinny”并不是绝对必要的，但没有造成任何伤害，并且它强制执行我们试图传达的信息。让我们继续 SVD： $m \gg n$

" ... 现在给定，我们最多可以使用算术运算来计算，矩阵的 SVD 。 $A = QR$ $R = U \Sigma V^T$ $O(n^3)$ $A = (QU)\Sigma V^T$ $A$

我不知道任何涵盖您的确切情况的专业术语。写一些类似的东西不会错

“翻牌数为，其中和。” $O(pq^2)$ $p=\max\{m,n\}$ $q=\min\{m,n\}$

但这并不像上面那样具有说明性。除非绝对必要，否则我会犹豫是否发明新术语。

其它你可能感兴趣的问题