Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
复制标题
在并行和分布式环境中实现随机矩阵算法
DOI：
10.1109/jproc.2015.2494219
复制
发表时间：
2015
影响因子：
20.6
通讯作者：
Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Jiyan Yang;Xiangrui Meng;Michael W. Mahoney
在这个大规模数据的时代，构建在商品硬件集群之上的分布式系统提供了廉价可靠的存储和可扩展的海量数据处理。使用廉价的存储，而不是只存储当前相关的数据，通常会存储尽可能多的数据，希望以后可以提取其价值。通过这种方式，每天都会创建EB（1018字节）的数据。然而，从这些数据中提取价值需要可扩展的高级分析算法的实现，而不仅仅是简单的数据处理，例如，统计回归方法、线性代数和优化算法。大多数这样的传统方法被设计为最小化浮点操作，这是在单个机器上的内存计算的主要成本。然而，在并行和分布式环境中，负载平衡和通信，包括磁盘和网络输入/输出（I/O），可以很容易地支配计算。这些因素极大地增加了算法设计的复杂性，并挑战了并行和分布式算法设计的传统思维方式。在这里，我们回顾了最近的工作，在大规模并行和分布式环境中开发和实现随机矩阵算法。近年来，矩阵问题的随机算法受到了极大的关注，迄今为止通常在理论上或机器学习应用中或在单个机器上实现。
In this era of large-scale data, distributed systems built on top of clusters of commodity hardware provide cheap and reliable storage and scalable processing of massive data. With cheap storage, instead of storing only currently relevant data, it is common to store as much data as possible, hoping that its value can be extracted later. In this way, exabytes (1018 bytes) of data are being created on a daily basis. Extracting value from these data, however, requires scalable implementations of advanced analytical algorithms beyond simple data processing, e.g., statistical regression methods, linear algebra, and optimization algorithms. Most such traditional methods are designed to minimize floating-point operations, which is the dominant cost of in-memory computation on a single machine. In parallel and distributed environments, however, load balancing and communication, including disk and network input/output (I/O), can easily dominate computation. These factors greatly increase the complexity of algorithm design and challenge traditional ways of thinking about the design of parallel and distributed algorithms. Here, we review recent work on developing and implementing randomized matrix algorithms in large-scale parallel and distributed environments. Randomized algorithms for matrix problems have received a great deal of attention in recent years, thus far typically either in theory or in machine learning applications or with implementations on a single machine.