解决 SDD 系统逼近最优解
提出了一种针对对称对角占优线性系统的改进算法,该算法利用图稀疏化和预处理来构建一条链以求解方程。同时,也介绍了一种构建近似最小 “拉伸” 生成树的算法,并证明了这两个算法的时间效率。
Feb, 2011
本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图,该算法基于三种新技术,并使用新的潜力函数,通过半定规划求解构造单侧频谱稀疏子图。
Feb, 2017
提出一种基于随机算法、适用于对称矩阵的预处理方法及线性系统求解器,其具低渐进复杂度;该算法中,递归运用子图预处理器来改进 Vaidya(1990)的子图预处理方法,当矩阵的非零结构为平面图时,求解器可以期望在时间 O(nlog²n + nlognloglognlog (1/ε))内运行。
Jul, 2006
本文介绍了一种简单的组合算法,它几乎在线性时间内解决了对称对角线优势(SDD)线性系统问题,而无需递归预处理、光谱稀疏化或更高精度。算法通过构建与线性系统相关的图的 “好” 生成树,并反复应用一个简单的(非递归的)更新规则来实现。该算法具有数值稳定性,而且不需要实现先前算法所需的增加位精度。因此,该算法在标准单位成本 RAM 模型下具有已知的最快运行时间。我们希望算法的简单性和分析所产生的洞见对理论和实践都有所帮助。
Jan, 2013
本文主要研究解决局部线性系统的亚线性算法,并比较了对称对角占优矩阵和半正定矩阵在坐标近似问题上的差异。通过开发出近似坐标的算法,我们证明了存在一定的定量差距,并证明条件数假设是必要且紧束缚的。相比于对称对角占优矩阵,我们证明了对于某些半正定矩阵,其运行时间必须是多项式级别的。
Sep, 2018
本文考虑保留原图的一个子图、寻找 k - 边加权图来加强原图的谱稀疏化问题,给出可行条件及多项式时间算法,并在超稀疏化问题和谱优化问题方面得出了应用结果。
Dec, 2009
介绍了一个基于奇异值估算子程序的量子算法,可解决线性方程组问题,其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时,所提出的算法的运行时间受到限制,其运行时间比已知的量子线性系统算法提高了平方级别。
Apr, 2017