提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

Dec, 2023

本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。

Nov, 2018

提出了一种针对对称对角占优线性系统的改进算法，该算法利用图稀疏化和预处理来构建一条链以求解方程。同时，也介绍了一种构建近似最小 “拉伸” 生成树的算法，并证明了这两个算法的时间效率。

Feb, 2011

本文介绍了一种简单的组合算法，它几乎在线性时间内解决了对称对角线优势（SDD）线性系统问题，而无需递归预处理、光谱稀疏化或更高精度。算法通过构建与线性系统相关的图的 “好” 生成树，并反复应用一个简单的（非递归的）更新规则来实现。该算法具有数值稳定性，而且不需要实现先前算法所需的增加位精度。因此，该算法在标准单位成本 RAM 模型下具有已知的最快运行时间。我们希望算法的简单性和分析所产生的洞见对理论和实践都有所帮助。

Jan, 2013

介绍了一个基于奇异值估算子程序的量子算法，可解决线性方程组问题，其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时，所提出的算法的运行时间受到限制，其运行时间比已知的量子线性系统算法提高了平方级别。

Apr, 2017

提出一种基于随机算法、适用于对称矩阵的预处理方法及线性系统求解器，其具低渐进复杂度；该算法中，递归运用子图预处理器来改进 Vaidya（1990）的子图预处理方法，当矩阵的非零结构为平面图时，求解器可以期望在时间 O（nlog²n + nlognloglognlog (1/ε)）内运行。

Jul, 2006

该研究探讨了解决稀疏矩阵线性系统的期望值问题，通过使用量子算法实现了在 poly (log N, kappa) 时间内运行，这是目前最佳经典算法的指数级改进。

Nov, 2008

本研究介绍了一种基于递增稀疏化的算法，可在输入 n 个顶点和 m 条边的加权图以及一个值 k 后，产生一个有限边数为 n-1+m/k 的递增稀疏化图，较好地维持了图的条件数，并以很快的速度求解出满足一定误差要求的向量，这一算法基于 Chebyshev 迭代和递归算法实现。

Mar, 2010

本篇研究文章探讨通过推荐算法，计算相似矩阵的问题，介绍了基于 Nyström 方法的一种新的推荐算法，此算法可以以亚线性时间的复杂度对任何相似矩阵进行求解，在 NLP 的不同应用场景中展示出高精确度的表现。

Dec, 2021

本研究提出了一种插值算法，该算法能够在两个特殊情况之间插值，并解决矩阵游戏问题。我们同时提供经典算法和量子算法，用于近似 Cara​théodore 问题和 lq-margin 支持向量机。

Dec, 2020