Jan, 2013

一个简单的组合算法，用于近线性时间解决 SDD 系统

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

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

    Feb, 2011

  • 解决 SDD 系统逼近最优解

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

    Mar, 2010

  • 关于亚线性时间求解线性系统

    本文主要研究解决局部线性系统的亚线性算法，并比较了对称对角占优矩阵和半正定矩阵在坐标近似问题上的差异。通过开发出近似坐标的算法，我们证明了存在一定的定量差距，并证明条件数假设是必要且紧束缚的。相比于对称对角占优矩阵，我们证明了对于某些半正定矩阵，其运行时间必须是多项式级别的。

    Sep, 2018

  • 对称、对角占优线性系统预处理和求解的几乎线性时间算法

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

    Jul, 2006

  • 解线性系统的高效加速坐标下降方法和更快的算法

    该论文介绍了如何加速随机坐标下降方法，提高收敛速度，同时又不用支付每次迭代的代价。它提出了一个新的通用方法，并证明它的收敛性，并在多个领域中获得更快的渐近运行时间。

    May, 2013

  • 随机对偶上升用于解线性系统

    提出了一种新的随机迭代算法 —— 随机对偶上升 (SDA)，用于在线性系统的解空间中找到给定向量的投影。该算法通过随机矩阵的列子空间上的精心选择点来更新对偶变量，并证明了与对偶过程相关的原始迭代会期望指数级别收敛至投影。SDA 收敛于一致性之外的无其他假设的线性系统，特殊情况下，该方法可用于分布式平均共识问题，产生各种新算法。

    Dec, 2015

  • 在高维线性系统中交替极小能量方法。第二部分：更快的算法和非对称系统的应用

    本文提出了一种快速的基于张量结构的对称正定线性系统求解方法，该方法采用能量函数交替最小化与基函数扩展步骤并结合最陡下降算法，进而实现了全局收敛和高效率求解。

    Apr, 2013

  • 结构化半定规划用于恢复结构化预条件器

    我们开发了一个普遍框架用于寻找解线性系统的近似最优预条件器，利用该框架，我们获得了优化预条件化和线性系统求解问题的运行时间改进。

    Oct, 2023

  • 使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

    本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。

    Jul, 2015

  • 高效求解密集线性系统的方法

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

    Dec, 2023