- 凸优化、凸凹博弈的改进切割平面方法及其应用
提出了一种新的剪切平面算法,采用多层数据结构来维护杠杆得分,通过随机投影,批量低秩更新,逆维护,多项式插值和快速矩阵乘法的复杂组合来实现,优化了以前算法的依赖性,并在经济学中的许多重要应用中实现了更好的性能。
- 在当前矩阵乘法时间内解决线性规划问题
本文介绍了一种解决线性规划问题的算法,旨在在对矩阵乘法进行研究后,以次二次时间复杂度解决规模为 n 的问题,同时提出了新的概念,如随机中心路径法和投影矩阵等。
- 对数直径轮并行图连通性
研究在 MPC 模型下对图连通性问题进行优化,通过图直径参数化时间复杂度,得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法,并扩展到生成森林、DFS 序列、最小生成森林 - NVIDIA Tensor Core 可编程性、性能和精度
本文介绍了 NVIDIA Volta GPU 微架构中一种特殊的处理器 Tensor Core,它能够在每个时钟周期内对 4x4 矩阵执行一个矩阵乘积累加操作,经过测试,我们发现 NVIDIA Tensor Core 在 Tesla V10 - MM用于分布式计算和滞后服务器的块对角和 LT 编码
本文介绍两种分布式计算方案:基于 MDS 代码的矩阵乘法分块编码方案和基于 Luby Transform 码的 inactivation 译码方案。数值结果表明,本文所提出的方案在截止日期内的性能优于文献中的其他方案。
- ICMLStrassenNets:带有乘法预算的深度学习
本研究介绍了一种使用二层求和乘积网络(SPN)的方法,通过学习从数据中的边缘权重(三元)来获得深度神经网络(DNN)层中矩阵乘法的低成本近似,同时应用知识蒸馏,实现对 DNN 中乘法操作数量的预算,从而在保持预测性能的同时,实现乘法操作数量 - NIPS核矩阵低秩逼近中是否存在稀疏化输入时间?
本文研究了计算有效的低秩核近似的限制,证明计算相对误差 k 秩逼近 K 对于广泛类别的核,包括高斯和多项式核,至少与将输入数据矩阵 A 乘以任意矩阵 C 一样困难,并给出了一些希望:首次证明对于一般的径向基函数核, 如高斯核,存在 $O ( - WWWSlashdot Zoo: 带负边的社交网络挖掘
本文通过对 Slashdot 技术新闻网站用户关系的语料库进行社交网络分析,研究了负边权的问题,考虑了全局网络特征,节点特征和链接特征等方面,用于识别不受欢迎的用户,预测链路符号,并展示了网络呈现乘性传递性,从而可以使用基于矩阵乘法的代数方 - 利用 Coppersmith-Winograd 张量的幂次改进矩阵乘法
本文提出一种利用张量幂次的对称和非对称结构实现矩阵乘法复杂度下界优化的新方法,通过分析 Coppersmith-Winograd 张量的四次幂进一步降低矩阵乘法复杂度下界,并得到了许多基于矩阵乘法的问题的新解法。
- 多项式码:高维编码矩阵乘法的最优设计
本研究提出了一种叫做 “多项式编码” 的计算策略,使用分布式系统(由主节点和多个工作节点组成)来进行大规模矩阵乘法计算,并通过利用编码理论的思想在工作节点上设计中间计算,以有效地处理延迟的工作节点,从而实现了恢复阈值的最优化,并在分布式卷积 - 超越快速矩阵乘法的频谱逼近:算法与难度
本文提出一项新的算法,使用随机痕量估计方法,多项式逼近,以及快速系统求解器等高效地获得一个矩阵的奇异值谱的直方图,并用其来求解一类对称矩阵范数。同时,证明了精度高的算法可以在次立方时间内进行矩阵乘法,从而限制了计算有效电阻的难度。
- 异构集群上的编码计算
本文提出了一种编码框架(HCMM)以提高异构分布式计算的速度,并展示了在 Amazon EC2 上进行分布式矩阵乘法实验的结果。该方法比三种基准负载分配方案的速度分别快 61%,46%和 36%。同时,我们还提供了在异构设置中的最优负载分配 - 使用稀疏卷积和指导剪枝加速 CNN
本文提出一种同时实现卷积神经网络的规模经济和速度提升的方法,包括一种有效的一般性稀疏 - 稠密矩阵乘法实现以及一种性能模型,可以预测不同层和不同计算机架构的稀疏水平的最佳值,该方法可在包括移动设备和超级计算机在内的各种处理器上实现 3.1- - 如何伪造由高斯矩阵相乘
本研究提出了新的随机化矩阵转换方法,用以快速计算矩阵乘法并保证计算效率,可以应用于非负矩阵分解和支持向量机等计算任务中。
- 关于帽集与矩阵乘法的群论方法
该论文通过限制阿贝尔群中三色无和集的大小,阐述了如何从阿贝尔群中获取矩阵乘法乘积的指数 $ω=2$ 的具体猜想,从而得出这一框架无法获得 $ω=2$ 的结论,并证明了 Tao 提出的张量秩的一个变体可以量化几何不变理论中的不稳定张量的概念。
- 基于随机哈希的可扩展可持续深度学习
提出了一种基于哈希的新技术,通过只处理少量的节点来显著降低训练和测试深度神经网络的计算成本,该算法只使用了原始模型总乘法数的 5%,同时保持平均精度在 1%以内,其更新始终是稀疏的,使得算法非常适合异步和并行训练,端到端实验展示了该算法的可 - NIPS使用编码加速分布式机器学习
探究编码算法在分布式机器学习中的应用,研究矩阵乘法和数据洗牌两种算法中应用编码技术减少 straggler 和 communication bottlenecks 时的优化效果,理论分析和实验结果均证明编码算法具有显著的优势。
- 张量的幂和快速矩阵乘法
该论文提出了一种基于凸优化的分析三线性形式的方法,从而得出矩阵乘法的渐近复杂性的上限,最终得到了比最佳已知上限略好的平方矩阵乘法指数的上界(ω<2.3728639)
- 电路评估的时间最优交互证明
本文描述了一种交互证明协议的改进方法,可以实现具有正确性保证的计算,效率比现有的实现提高了 200 倍,在矩阵乘法和数据并行计算方面也有应用。
- Map-Reduce 计算成本的上下界
本文探讨了在 map-reduce 计算中并行性和通信成本之间的权衡问题,并引入了单轮 map-reduce 计算问题的模型,以发现以分配给一个缩小器的最大输入数为函数的通信成本下界。作者对三个问题进行了分析:找到两个距离为 $d$ 的字符