BriefGPT.xyz
Dec, 2023
高效求解密集线性系统的方法
Solving Dense Linear Systems Faster than via Preconditioning
HTML
PDF
Michał Dereziński, Jiaming Yang
TL;DR
提出了一种随机优化算法,通过块坐标下降方法和矩阵草图技术,在线性系统中实现了良好的收敛性能和快速迭代时间。
Abstract
We give a
stochastic optimization
algorithm that solves a dense $n\times n$ real-valued
linear system
$Ax=b$, returning $\tilde x$ such that $\|A\tilde x-b\|\leq \epsilon\|b\|$ in time: $$\tilde O((n^2+nk^{\omega
→