SDD 线性系统的近乎 O (mlogn) 求解器
提出一种基于随机算法、适用于对称矩阵的预处理方法及线性系统求解器,其具低渐进复杂度;该算法中,递归运用子图预处理器来改进 Vaidya(1990)的子图预处理方法,当矩阵的非零结构为平面图时,求解器可以期望在时间 O(nlog²n + nlognloglognlog (1/ε))内运行。
Jul, 2006
本研究介绍了一种基于递增稀疏化的算法,可在输入 n 个顶点和 m 条边的加权图以及一个值 k 后,产生一个有限边数为 n-1+m/k 的递增稀疏化图,较好地维持了图的条件数,并以很快的速度求解出满足一定误差要求的向量,这一算法基于 Chebyshev 迭代和递归算法实现。
Mar, 2010
本文介绍了一种简单的组合算法,它几乎在线性时间内解决了对称对角线优势(SDD)线性系统问题,而无需递归预处理、光谱稀疏化或更高精度。算法通过构建与线性系统相关的图的 “好” 生成树,并反复应用一个简单的(非递归的)更新规则来实现。该算法具有数值稳定性,而且不需要实现先前算法所需的增加位精度。因此,该算法在标准单位成本 RAM 模型下具有已知的最快运行时间。我们希望算法的简单性和分析所产生的洞见对理论和实践都有所帮助。
Jan, 2013
本文主要研究解决局部线性系统的亚线性算法,并比较了对称对角占优矩阵和半正定矩阵在坐标近似问题上的差异。通过开发出近似坐标的算法,我们证明了存在一定的定量差距,并证明条件数假设是必要且紧束缚的。相比于对称对角占优矩阵,我们证明了对于某些半正定矩阵,其运行时间必须是多项式级别的。
Sep, 2018
介绍了一个基于奇异值估算子程序的量子算法,可解决线性方程组问题,其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时,所提出的算法的运行时间受到限制,其运行时间比已知的量子线性系统算法提高了平方级别。
Apr, 2017
本文为矩阵缩放问题开发了多种有效的算法,并着重解决了一些特殊情况。该算法的复杂度为总复杂度 $\tilde {O}(m + n^{4/3})$,这比之前最好的精度 $\tilde {O}(n^4)$ 或 $O (m n^{1/2}/\varepsilon)$ 都要大大提高。
Apr, 2017
我们介绍了一种新的预条件化迭代方法类别,用于解决线性系统的求解问题,并基于使用稀疏随机草图构建对 A 的低秩 Nyström 近似。我们证明,我们的方法的收敛性取决于 A 的自然平均条件数,该条件数随着 Nyström 近似的秩增加而改善。具体而言,这使得我们能够以更快的速度解决许多基本的线性代数问题,并且我们的工作采用完全不同的方法,利用矩阵缩略图工具。
May, 2024
本文通过使用低秩更新、预处理和快速矩阵乘法等经典数值技术,结合近期关于子空间嵌入和谱稀疏化的研究,提出了解决逆维护问题的新方法,并获得了最快的解决多个问题的运行时间,包括线性规划和计算单形体的舍入。
Mar, 2015