Question

我们在下面的矩阵中采用线性组合（带有随机权重）：

plt.figure(figsize=(12, 12))
plt.imshow(M, cmap='gray')

# <matplotlib.image.AxesImage at 0x7f601f315fd0>

这就像一个随机加权平均值。 如果你选取其中的几个，你最终会得到彼此不高度相关的列（大致正交）。

Johnson-Lindenstrauss 引理：（来自维基百科）高维空间中的一小组点可以嵌入到更低维度的空间中，使得点之间的距离几乎保持不变。

我们期望，能够以保留相关结构的方式，减少数据的维度。 Johnson-Lindenstrauss 引理是这种类型的经典结果。

高斯消元的历史

有趣的事实：高斯并没有发明高斯消元，但可能在 Cholesky 之前发现了 Cholesky 因子分解

— Rachel Thomas (@math_rachel) 2017 年 6 月 6 日

根据维基百科， Stigler 的 Eponymy 定律 ：“没有任何科学发现以它的原始发现者命名。例子包括哈勃定律，它是由 Georges Lemaître 在 Edwin Hubble 两年之前得到的，毕达哥拉斯定理在毕达哥拉斯之前为巴比伦数学家所知，哈雷彗星是自公元前 240 年以来天文学家观察到的彗星。Stigler 本人将社会学家 Robert K. Merton 命名为 Stigler 定律的发现者，表明它遵循自己的法令，尽管这一现象之前曾被其他人注意到。”

迷人的高斯消元的历史 。一些亮点：

• 公元前 20 0 年左右，高斯消元的第一个书面记录在中文书籍“九章算术”中。
• 古代中国人使用彩色竹棒放在“计数板”的列中。
• 日本数学家 Seki Kowa（1643-1708）在 1683 年之前推进了中国的淘汰消元，并发明了行列式。大约在同一时间，莱布尼兹独立地发现了相似的发现，但是 Kowa 和莱布尼兹都没有因为他们的发现而受到赞扬。
• 高斯称消元方法是“众所周知的”并且从未声称已经发明了它，尽管他可能已经发明了 Cholesky 分解。

这里有更多历史

加速高斯消元

并行 LU 分解 ：LU 分解可以完全并行化

随机化 LU 分解 （2016 年文章）：随机 LU 完全为在标准 GPU 上运行而实现，无需任何 GPU-CPU 数据传输。

scipy.linalg vs lu_solve

n = 60
A = make_matrix(n)
b = make_vector(n)

这个问题有很大的增长因子 = 259 。 我们使用 scipy.linalg.lu_solve 获得了错误的答案，但使用 scipy.linalg.solve 得到了正确的答案。什么是 scipy.linalg.solve 呢？

print(scipy.linalg.lu_solve(scipy.linalg.lu_factor(A), b)[-5:])
print(scipy.linalg.solve(A, b)[-5:])

'''
[ 0.  0.  0.  0.  1.]
[-0.062 -0.125 -0.25   0.5    1.   ]
'''

%%timeit
soln = scipy.linalg.lu_solve(scipy.linalg.lu_factor(A), b)
soln[-5:]

# 91.2 µs ± 192 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%%timeit
soln = scipy.linalg.solve(A, b)
soln[-5:]

# 153 µs ± 5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

查看 scipy 的源代码，我们看到它正在调用 LAPACK 例程 gesvx 。 这是 sgesvx 的 Fortran 源代码（ s 指的是单个，也有用于浮点的 dgesvx 和复数的 cgesvx ）。 在注释中，我们看到它正在计算 reciprocal 主元增长因子，因此它考虑了这个增长因子，并做了一些比普通的部分主元 LU 分解更复杂的事情。