44 results on '"Ballard, Grey"'
Search Results
2. PARALLEL RANDOMIZED TUCKER DECOMPOSITION ALGORITHMS.
- Author
-
MINSTER, RACHEL, ZITONG LI, and BALLARD, GREY
- Subjects
SINGULAR value decomposition ,RANDOM matrices ,ALGORITHMS ,PARALLEL algorithms ,APPROXIMATION error ,MULTILINEAR algebra - Abstract
The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. We propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. COMMUNICATION LOWER BOUNDS AND OPTIMAL ALGORITHMS FOR MULTIPLE TENSOR-TIMES-MATRIX COMPUTATION.
- Author
-
AL DAAS, HUSSAM, BALLARD, GREY, GRIGORI, LAURA, KUMAR, SURAJ, and ROUSE, KATHRYN
- Subjects
- *
PARALLEL algorithms , *ALGORITHMS , *NONLINEAR equations , *DATA analysis - Abstract
Multiple tensor-times-matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine how much data movement is required (under mild conditions) to perform the Multi-TTM computation in parallel. The crux of the proof relies on analytically solving a constrained, nonlinear optimization problem. We also present a parallel algorithm to perform this computation that organizes the processors into a logical grid with twice as many modes as the input tensor. We show that, with correct choices of grid dimensions, the communication cost of the algorithm attains the lower bounds and is therefore communication optimal. Finally, we show that our algorithm can significantly reduce communication compared to the straightforward approach of expressing the computation as a sequence of tensor-times-matrix operations when the input and output tensors vary greatly in size. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. CP decomposition for tensors via alternating least squares with QR decomposition.
- Author
-
Minster, Rachel, Viviano, Irina, Liu, Xiaotian, and Ballard, Grey
- Subjects
LEAST squares ,SINGULAR value decomposition ,APPROXIMATION error ,UNITS of time ,MULTILINEAR algebra ,LATENT structure analysis - Abstract
The CP tensor decomposition is used in applications such as machine learning and signal processing to discover latent low‐rank structure in multidimensional data. Computing a CP decomposition via an alternating least squares (ALS) method reduces the problem to several linear least squares problems. The standard way to solve these linear least squares subproblems is to use the normal equations, which inherit special tensor structure that can be exploited for computational efficiency. However, the normal equations are sensitive to numerical ill‐conditioning, which can compromise the results of the decomposition. In this paper, we develop versions of the CP‐ALS algorithm using the QR decomposition and the singular value decomposition, which are more numerically stable than the normal equations, to solve the linear least squares problems. Our algorithms utilize the tensor structure of the CP‐ALS subproblems efficiently, have the same complexity as the standard CP‐ALS algorithm when the input is dense and the rank is small, and are shown via examples to produce more stable results when ill‐conditioning is present. Our MATLAB implementation achieves the same running time as the standard algorithm for small ranks, and we show that the new methods can obtain lower approximation error. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Parallel Randomized Tucker Decomposition Algorithms
- Author
-
Minster, Rachel, Li, Zitong, and Ballard, Grey
- Subjects
FOS: Mathematics ,Numerical Analysis (math.NA) ,Mathematics - Numerical Analysis - Abstract
The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. We propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data.
- Published
- 2022
6. Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation
- Author
-
Daas, Hussam Al, Ballard, Grey, Grigori, Laura, Kumar, Suraj, Rouse, Kathryn, STFC Rutherford Appleton Laboratory (RAL), Science and Technology Facilities Council (STFC), Wake Forest University, Algorithms and parallel tools for integrated numerical simulations (ALPINES), Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Inmar Intelligence, This work is supported by the National Science Foundation under Grant No. CCF-1942892 and OAC-2106920. This project also has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant agreement No. 810367)., and European Project: 810367,EMC2(2019)
- Subjects
FOS: Computer and information sciences ,Communication lower bounds ,Tensor computations ,Multi-TTM ,Computer Science - Distributed, Parallel, and Cluster Computing ,Parallel algorithms ,MSC codes. 15A69, 68Q17, 68Q25, 68W10, 68W15, 68W40 ,[INFO]Computer Science [cs] ,Distributed, Parallel, and Cluster Computing (cs.DC) ,HBL-inequalities - Abstract
Multiple Tensor-Times-Matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine how much data movement is required to perform the Multi-TTM computation in parallel. The crux of the proof relies on analytically solving a constrained, nonlinear optimization problem. We also present a parallel algorithm to perform this computation that organizes the processors into a logical grid with twice as many modes as the input tensor. We show that with correct choices of grid dimensions, the communication cost of the algorithm attains the lower bounds and is therefore communication optimal. Finally, we show that our algorithm can significantly reduce communication compared to the straightforward approach of expressing the computation as a sequence of tensor-times-matrix operations.
- Published
- 2022
7. Dynamic functional connectivity and individual differences in emotions during social stress
- Author
-
Tobia, Michael J., Hayashi, Koby, Ballard, Grey, Gotlib, Ian H., and Waugh, Christian E.
- Published
- 2017
- Full Text
- View/download PDF
8. RANDOMIZED ALGORITHMS FOR ROUNDING IN THE TENSOR-TRAIN FORMAT.
- Author
-
AL DAAS, HUSSAM, BALLARD, GREY, CAZEAUX, PAUL, HALLMAN, ERIC, MIĘDLAR, AGNIESZKA, PASHA, MIRJETA, REID, TIM W., and SAIBABA, ARVIND K.
- Subjects
- *
DETERMINISTIC algorithms , *PARTIAL differential equations , *APPROXIMATION algorithms , *ALGORITHMS , *LOW-rank matrices - Abstract
The tensor-train (TT) format is a highly compact low-rank representation for highdimensional tensors. TT is particularly useful when representing approximations to the solutions of certain types of parametrized partial differential equations. For many of these problems, computing the solution explicitly would require an infeasible amount of memory and computational time. While the TT format makes these problems tractable, iterative techniques for solving the PDEs must be adapted to perform arithmetic while maintaining the implicit structure. The fundamental operation used to maintain feasible memory and computational time is called rounding, which truncates the internal ranks of a tensor already in TT format. We propose several randomized algorithms for this task that are generalizations of randomized low-rank matrix approximation algorithms and provide significant reduction in computation compared to deterministic TT-rounding algorithms. Randomization is particularly effective in the case of rounding a sum of TT-tensors (where we observe 20\times speedup), which is the bottleneck computation in the adaptation of GMRES to vectors in TT format. We present the randomized algorithms and compare their empirical accuracy and computational time with deterministic alternatives. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. Avoiding Communication in Dense Linear Algebra
- Author
-
Ballard, Grey
- Subjects
Computer science ,Applied mathematics ,algorithms ,communication-avoiding ,matrix computations - Abstract
Dense linear algebra computations are essential to nearly every problem in scientific computing and to countless other fields. Most matrix computations enjoy a high computational intensity (i.e., ratio of computation to data), and therefore the algorithms for the computations have a potential for high efficiency. However, performance for many linear algebra algorithms is limited by the cost of moving data between processors on a parallel computer or throughout the memory hierarchy of a single processor, which we will refer to generally as communication. Technological trends indicate that algorithmic performance will become even more limited by communication in the future. In this thesis, we consider the fundamental computations within dense linear algebra and address the following question: can we significantly improve the current algorithms for these computations, in terms of the communication they require and their performance in practice?To answer the question, we analyze algorithms on sequential and parallel architectural models that are simple enough to determine coarse communication costs but accurate enough to predict performance of implementations on real hardware. For most of the computations, we prove lower bounds on the communication that any algorithm must perform. If an algorithm exists with communication costs that match the lower bounds (at least in an asymptotic sense), we call the algorithm communication optimal. In many cases, the most commonly used algorithms are not communication optimal, and we can develop new algorithms that require less data movement and attain the communication lower bounds.In this thesis, we develop both new communication lower bounds and new algorithms, tightening (and in many cases closing) the gap between best known lower bound and best known algorithm (or upper bound). We consider both sequential and parallel algorithms, and we asses both classical and fast algorithms (e.g., Strassen's matrix multiplication algorithm).In particular, the central contributions of this thesis are: proving new communication lower bounds for nearly all classical direct linear algebra computations (dense or sparse), including factorizations for solving linear systems, least squares problems, and eigenvalue and singular value problems; proving new communication lower bounds for Strassen's and other fast matrix multiplication algorithms; proving new parallel communication lower bounds for classical and fast computations that set limits on an algorithm's ability to perfectly strong scale; summarizing the state-of-the-art in communication efficiency for both sequential and parallel algorithms for the computations to which the lower bounds apply; developing a new communication-optimal algorithm for computing a symmetric-indefinite factorization (observing speedups of up to 2.8x compared to alternative shared-memory parallel algorithms); developing new, more communication-efficient algorithms for reducing a symmetric band matrix to tridiagonal form via orthogonal similar transformations (observing speedups of 2--6x compared to alternative sequential and parallel algorithms); and developing a new communication-optimal parallelization of Strassen's matrix multiplication algorithm (observing speedups of up to 2.84x compared to alternative distributed-memory parallel algorithms).
- Published
- 2013
10. PARALLEL ALGORITHMS FOR TENSOR TRAIN ARITHMETIC.
- Author
-
AL DAAS, HUSSAM, BALLARD, GREY, and BENNER, PETER
- Subjects
- *
ARITHMETIC , *PARALLEL algorithms , *DATA distribution , *MULTIPLICATION , *ALGORITHMS , *SCALABILITY - Abstract
We present efficient and scalable parallel algorithms for performing mathematical operations for low-rank tensors represented in the tensor train (TT) format. We consider algorithms for addition, elementwise multiplication, computing norms and inner products, orthonormalization, and rounding (rank truncation). These are the kernel operations for applications such as iterative Krylov solvers that exploit the TT structure. The parallel algorithms are designed for distributedmemory computation, and we propose a data distribution and strategy that parallelizes computations for individual cores within the TT format. We analyze the computation and communication costs of the proposed algorithms to show their scalability, and we present numerical experiments that demonstrate their efficiency on both shared-memory and distributed-memory parallel systems. For example, we observe better single-core performance than the existing MATLAB TT-Toolbox in rounding a 2GB TT tensor, and our implementation achieves a 34× speedup using all 40 cores of a single node. We also show nearly linear parallel scaling on larger TT tensors up to over 10,000 cores for all mathematical operations. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. PLANC: Parallel Low-rank Approximation with Nonnegativity Constraints.
- Author
-
Eswar, Srinivas, Hayashi, Koby, Ballard, Grey, Kannan, Ramakrishnan, Matheson, Michael A., and Park, Haesun
- Subjects
ALGORITHMS ,PARALLEL programming ,DISTRIBUTION (Probability theory) ,INTEGRATED software ,GRAPHICS processing units ,PARALLEL algorithms ,SCALABILITY - Abstract
We consider the problem of low-rank approximation of massive dense nonnegative tensor data, for example, to discover latent patterns in video and imaging applications. As the size of data sets grows, single workstations are hitting bottlenecks in both computation time and available memory. We propose a distributed-memory parallel computing solution to handle massive data sets, loading the input data across the memories of multiple nodes, and performing efficient and scalable parallel algorithms to compute the low-rank approximation. We present a software package called Parallel Low-rank Approximation with Nonnegativity Constraints, which implements our solution and allows for extension in terms of data (dense or sparse, matrices or tensors of any order), algorithm (e.g., from multiplicative updating techniques to alternating direction method of multipliers), and architecture (we exploit GPUs to accelerate the computation in this work). We describe our parallel distributions and algorithms, which are careful to avoid unnecessary communication and computation, show how to extend the software to include new algorithms and/or constraints, and report efficiency and scalability results for both synthetic and real-world data sets. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
12. Partitioning and Communication Strategies for Sparse Non-negative Matrix Factorization
- Author
-
Kaya, Oguz, Kannan, Ramakrishnan, Ballard, Grey, High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Oak Ridge National Laboratory [Oak Ridge] (ORNL), UT-Battelle, LLC, Department of Mathematics, Wake Forest University, and Inria Bordeaux Sud-Ouest
- Subjects
Parallel algorithms ,Partitionnement d'hypergraphes ,Hypergraph partitioning ,Algorithmique parallèle ,Factorisation de matrice non-negative creuse ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Sparse non-negative matrix factorization - Abstract
Non-negative matrix factorization (NMF), the problem of finding two non-negative low-rank factors whose product approximates an input matrix, is a useful tool for many data mining and scientific applications such as topic modeling in text mining and blind source separation in microscopy.In this paper, we focus on scaling algorithms for NMF to very large sparse datasets and massively parallel machines by employing effective algorithms, communication patterns, and partitioning schemes that leverage the sparsity of the input matrix. In the case of machine learning workflow, the computations after SpMM must deal with dense matrices, as Sparse-Dense matrix multiplication will result in a dense matrix. Hence, the partitioning strategy considering only SpMM will result in a huge imbalance in the overall workflow especially on computations after SpMM and in this specific case of NMF on non-negative least squares computations. Towards this, we consider two previous works developed for related problems, one that uses a fine-grained partitioning strategy using a point-to-point communication pattern and on that uses a checkerboard partitioning strategy using a collective-based communication pattern.We show that a combination of the previous approaches balances the demands of the various computations within NMF algorithms and achieves high efficiency and scalability. From the experiments, we could see that our proposed algorithm communicates atleast 4x less than the collective and achieves upto 100x speed up over the baseline FAUN on real world datasets. Our algorithm was experimented in two different super computing platforms and we could scale up to 32000 processors on Bluegene/Q.; La factorisation de matrice non-négative (NMF), le problème de trouver deux facteurs de rang faible non négatifs dont le produit se rapproche d'une matrice d'entrée, est un outil utile pour de nombreuses applications scientifiques et d'exploration de données telles que la modélisation de textes et la séparation de signaux en microscopie.Dans cet article, nous etudions les algorithmes passant à l'échelle pour NMF à de très grands ensembles de données creuses et des machines massivement parallèles en utilisant des algorithmes efficaces, des modèles de communication et des schémas de partitionnement qui exploitent la structure creuse de la matrice.Dans le cadre de cet algorithme, les calculs après SpMM doivent traiter des matrices denses, car la multiplication SpMM produira une matrice dense.Par conséquent, la stratégie de partitionnement ne prenant en compte que SpMM entraînera un déséquilibre énorme dans l'algorithme global, en particulier sur les calculs après SpMM et dans ce cas spécifique de NMF sur les calculs de moindres carrés non négatifs.À cet égard, nous considérons deux travaux antérieurs développés pour des problèmes connexes, l'un utilisant une stratégie de partitionnement de granularité ffine utilisant un modèle de communication ``point-to-point'' et utilisant une stratégie de partitionnement en damier utilisant un modèle de communication collectif.Nous montrons qu'une combinaison des approches précédentes permet d'équilibrer les exigences des divers calculs au sein des algorithmes NMF et permet d'obtenir une efficacité et une évolutivité élevées. À partir des expériences, nous avons constaté que notre algorithme proposé communique au moins4x moins que le collectif et atteint jusqu'à 100 fois la vitesse de base sur les jeux de données réels. Notre algorithme a été expérimenté sur deux plates-formes superinformatiques différentes et nous avons pu passer à 32 000 processeurs sur Bluegene / Q.
- Published
- 2018
13. Graph Expansion and Communication Costs of Fast Matrix Multiplication.
- Author
-
BALLARD, GREY, DEMMEL, JAMES, HOLTZ, OLGA, and SCHWARTZ, ODED
- Subjects
MATRIX multiplications ,MATRICES (Mathematics) ,ALGORITHMS ,ARITHMETIC ,MATHEMATICS ,ALGEBRA - Abstract
The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs.We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain the first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size M, too small to store three n-by-n matrices, the lower bound on the number of words moved between fast and slow memory is, for a large class of matrix multiplication algorithms, Ω((n/√M)
ω0 ·M), where ω0 is the exponent in the arithmetic count (e.g., ω0 = lg 7 for Strassen, and ω0 = 3 for conventional matrix multiplication). With p parallel processors, each with fast memory of size M, the lower bound is asymptotically lower by a factor of p. These bounds are attainable both for sequential and for parallel algorithms and hence optimal. [ABSTRACT FROM AUTHOR]- Published
- 2012
- Full Text
- View/download PDF
14. TuckerMPI: A Parallel C++/MPI Software Package for Large-scale Data Compression via the Tucker Tensor Decomposition.
- Author
-
Ballard, Grey, Klinvex, Alicia, and Kolda, Tamara G.
- Subjects
- *
DATA compression , *COMPUTER software , *SINGULAR value decomposition , *IMAGE compression , *DATA distribution , *MATRIX decomposition , *PARALLEL programming - Abstract
Our goal is compression of massive-scale grid-structured data, such as the multi-terabyte output of a high-fidelity computational simulation. For such data sets, we have developed a new software package called TuckerMPI, a parallel C++/MPI software package for compressing distributed data. The approach is based on treating the data as a tensor, i.e., a multidimensional array, and computing its truncated Tucker decomposition, a higher-order analogue to the truncated singular value decomposition of a matrix. The result is a low-rank approximation of the original tensor-structured data. Compression efficiency is achieved by detecting latent global structure within the data, which we contrast to most compression methods that are focused on local structure. In this work, we describe TuckerMPI, our implementation of the truncated Tucker decomposition, including details of the data distribution and in-memory layouts, the parallel and serial implementations of the key kernels, and analysis of the storage, communication, and computational costs. We test the software on 4.5 and 6.7 terabyte data sets distributed across 100 s of nodes (1,000 s of MPI processes), achieving compression ratios between 100 and 200,000×, which equates to 99--99.999% compression (depending on the desired accuracy) in substantially less time than it would take to even read the same dataset from a parallel file system. Moreover, we show that our method also allows for reconstruction of partial or down-sampled data on a single node, without a parallel computer so long as the reconstructed portion is small enough to fit on a single machine, e.g., in the instance of reconstructing/visualizing a single down-sampled time step or computing summary statistics. The code is available at https://gitlab.com/tensors/TuckerMPI. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
15. Numerical Linear Algebra with Applications: Using MATLAB William Ford
- Author
-
Ballard, Grey
- Published
- 2015
16. Communication Costs of Strassen's Matrix Multiplication.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Subjects
- *
ALGORITHMS , *RUN time systems (Computer science) , *MEMORY hierarchy (Computer science) , *COMPUTER input-output equipment , *PARALLEL algorithms , *MATRICES (Mathematics) , *COMMUNICATION models , *PARTITIONS (Mathematics) , *RECURSIVE functions - Abstract
Algorithms have historically been evaluated in terms of the number of arithmetic operations they performed. This analysis is no longer sufficient for predicting running times on today's machines. Moving data through memory hierarchies and among processors requires much more time (and energy) than performing computations. Hardware trends suggest that the relative costs of this communication will only increase. Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are therefore fundamental goals. We show that the communication cost of an algorithm is closely related to the graph expansion properties of its corresponding computation graph. Matrix multiplication is one of the most fundamental problems in scientific computing and in parallel computing. Applying expansion analysis to Strassen's and other fast matrix multiplication algorithms, we obtain the first lower bounds on their communication costs. These bounds show that the current sequential algorithms are optimal but that previous parallel algorithms communicate more than necessary. Our new parallelization of Strassen's algorithm is communication-optimal and outperforms all previous matrix multiplication algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
17. Dynamic Functional Magnetic Resonance Imaging Connectivity Tensor Decomposition: A New Approach to Analyze and Interpret Dynamic Brain Connectivity.
- Author
-
Mokhtari, Fatemeh, Laurienti, Paul J., Rejeski, W. Jack, and Ballard, Grey
- Published
- 2019
- Full Text
- View/download PDF
18. A PRACTICAL RANDOMIZED CP TENSOR DECOMPOSITION.
- Author
-
BATTAGLINO, CASEY, BALLARD, GREY, and KOLDA, TAMARA G.
- Subjects
- *
LEAST squares , *MULTILINEAR algebra , *CHEMOMETRICS , *SIGNAL processing , *INTERNET traffic - Abstract
The CANDECOMP/PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show that the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri--Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
19. MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization.
- Author
-
Kannan, Ramakrishnan, Ballard, Grey, and Park, Haesun
- Subjects
- *
MATRICES (Mathematics) , *NUMERICAL analysis , *MATHEMATICAL analysis , *DATA mining , *ALGORITHMS - Abstract
Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors \mathbfW
, for the given input matrix \mathbfA , such that \mathbfA\approx \mathbfW\mathbfH and \mathbfH- Published
- 2018
- Full Text
- View/download PDF
20. Parallel Tensor Compression for Large-Scale Scientific Data.
- Author
-
Austin, Woody, Ballard, Grey, and Kolda, Tamara G.
- Published
- 2016
- Full Text
- View/download PDF
21. IMPROVING THE NUMERICAL STABILITY OF FAST MATRIX MULTIPLICATION.
- Author
-
BALLARD, GREY, BENSON, AUSTIN R., DRUINSKY, ALEX, LIPSHITZ, BENJAMIN, and SCHWARTZ, ODED
- Subjects
- *
MATRIX multiplications , *STABILITY theory , *NUMERICAL analysis , *MATHEMATICAL bounds , *ALGORITHMS - Abstract
Fast algorithms for matrix multiplication, namely those that perform asymptotically fewer scalar operations than the classical algorithm, have been considered primarily of theoretical interest. Apart from Strassen's original algorithm, few fast algorithms have been efficiently im- plemented or used in practical applications. However, there exist many practical alternatives to Strassen's algorithm with varying performance and numerical properties. Fast algorithms are known to be numerically stable, but because their error bounds are slightly weaker than the classical al- gorithm, they are not used even in cases where they provide a performance benefit. We argue in this paper that the numerical sacrifice of fast algorithms, particularly for the typical use cases of practical algorithms, is not prohibitive, and we explore ways to improve the accuracy both theoret- ically and empirically. The numerical accuracy of fast matrix multiplication depends on properties of the algorithm and of the input matrices, and we consider both contributions independently. We generalize and tighten previous error analyses of fast algorithms and compare their properties. We discuss algorithmic techniques for improving the error guarantees from two perspectives: manipulat- ing the algorithms, and reducing input anomalies by various forms of diagonal scaling. Finally, we benchmark performance and demonstrate our improved numerical accuracy. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
22. EXPLOITING MULTIPLE LEVELS OF PARALLELISM IN SPARSE MATRIX-MATRIX MULTIPLICATION.
- Author
-
AZAD, ARIFUL, BALLARD, GREY, BULUÇ, AYDIN, DEMMEL, JAMES, GRIGORI, LAURA, SCHWARTZ, ODED, TOLEDO, SIVAN, and WILLIAMS, SAMUEL
- Subjects
- *
SPARSE matrices , *MATRICES (Mathematics) , *MULTIPLICATION - Abstract
Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdös--Rényi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
23. Diamond Sampling for Approximate Maximum All-Pairs Dot-Product (MAD) Search.
- Author
-
Ballard, Grey, Kolda, Tamara G., Pinar, Ali, and Seshadhri, C.
- Published
- 2015
- Full Text
- View/download PDF
24. A high-performance parallel algorithm for nonnegative matrix factorization.
- Author
-
Kannan, Ramakrishnan, Ballard, Grey, and Park, Haesun
- Published
- 2016
- Full Text
- View/download PDF
25. REDUCING COMMUNICATION COSTS FOR SPARSE MATRIX MULTIPLICATION WITHIN ALGEBRAIC MULTIGRID.
- Author
-
BALLARD, GREY, SIEFERT, CHRISTOPHER, and JONATHAN HU
- Subjects
- *
COMMUNICATION , *COST , *ALGEBRA , *MULTIPLICATION , *ALGORITHMS - Abstract
We consider the sequence of sparse matrix-matrix multiplications performed during the setup phase of algebraic multigrid. In particular, we show that the most commonly used parallel algorithm is often not the most communication-efficient one for all of the matrix-matrix multiplica- tions involved. By using an alternative algorithm, we show that the communication costs are reduced (in theory and practice), and we demonstrate the performance benefit for both model (structured) and more realistic unstructured problems on large-scale distributed-memory parallel systems. Our theoretical analysis shows that we can reduce communication by a factor of up to 5.4 for a model problem, and we observe in our empirical evaluation communication reductions of factors up to 4.7 for structured problems and 3.7 for unstructured problems. These reductions in communication translate to run-time speedups of factors up to 2.8 and 2.5, respectively. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
26. Reconstructing Householder Vectors from Tall-Skinny QR.
- Author
-
Ballard, Grey, Demmel, James, Grigori, Laura, Jacquelin, Mathias, Nguyen, Hong Diep, and Solomonik, Edgar
- Published
- 2014
- Full Text
- View/download PDF
27. COMMUNICATION-AVOIDING SYMMETRIC-INDEFINITE FACTORIZATION.
- Author
-
BALLARD, GREY, BECKER, DULCENEIA, DEMMEL, JAMES, DONGARRA, JACK, DRUINSKY, ALEX, PELED, INON, SCHWARTZ, ODED, TOLEDO, SIVAN, and ICHITARO YAMAZAKI
- Subjects
- *
MATHEMATICAL symmetry , *FACTORIZATION , *TRIANGULARIZATION (Mathematics) , *MATRICES (Mathematics) , *OPTIMAL control theory - Abstract
We describe and analyze a novel symmetric triangular factorization algorithm. The algorithm is essentially a block version of Aasen's triangular tridiagonalization. It factors a dense symmetric matrix A as the product A = PLTLT PT, where P is a permutation matrix, L is lower triangular, and T is block tridiagonal and banded. The algorithm is the first symmetric-indefinite communication-avoiding factorization: it performs an asymptotically optimal amount of communication in a two-level memory hierarchy for almost any cache-line size. Adaptations of the algorithm to parallel computers are likely to be communication efficient as well; one such adaptation has been recently published. The current paper describes the algorithm, proves that it is numerically stable, and proves that it is communication optimal. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
28. Implementing a Blocked Aasen's Algorithm with a Dynamic Scheduler on Multicore Architectures.
- Author
-
Ballard, Grey, Becker, Dulceneia, Demmel, James, Dongarra, Jack, Druinsky, Alex, Peled, Inon, Schwartz, Oded, Toledo, Sivan, and Yamazaki, Ichitaro
- Published
- 2013
- Full Text
- View/download PDF
29. Communication-optimal parallel algorithm for strassen's matrix multiplication.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Published
- 2012
- Full Text
- View/download PDF
30. Communication-avoiding parallel strassen.
- Author
-
Lipshitz, Benjamin, Ballard, Grey, Demmel, James, and Schwartz, Oded
- Published
- 2012
31. Communication-Avoiding Parallel Strassen: Implementation and performance.
- Author
-
Lipshitz, Benjamin, Ballard, Grey, Demmel, James, and Schwartz, Oded
- Abstract
Matrix multiplication is a fundamental kernel of many high performance and scientific computing applications. Most parallel implementations use classical O(n3) matrix multiplication, even though there exist algorithms with lower arithmetic complexity. We recently presented a new Communication-Avoiding Parallel Strassen algorithm (CAPS), based on Strassen's fast matrix multiplication, that minimizes communication (SPAA'12). It communicates asymptotically less than all classical and all previous Strassen-based algorithms, and it attains theoretical lower bounds. In this paper we show that CAPS is also faster in practice. We benchmark and compare its performance to previous algorithms on Hopper (Cray XE6), Intrepid (IBM BG/P), and Franklin (Cray XT4). We demonstrate significant speedups over previous algorithms both for large matrices and for small matrices on large numbers of processors. We model and analyze the performance of CAPS and predict its performance on future exascale platforms. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
32. Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Published
- 2012
- Full Text
- View/download PDF
33. Graph expansion and communication costs of fast matrix multiplication.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Published
- 2011
- Full Text
- View/download PDF
34. Communication-optimal parallel and sequential Cholesky decomposition.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Published
- 2009
- Full Text
- View/download PDF
35. Communication avoiding successive band reduction.
- Author
-
Ballard, Grey, Demmel, James, and Knight, Nicholas
- Published
- 2012
- Full Text
- View/download PDF
36. MINIMIZING COMMUNICATION IN NUMERICAL LINEAR ALGEBRA.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, and Schwartz, Oded
- Subjects
- *
LINEAR algebra , *NUMERICAL analysis , *MATHEMATICAL proofs , *MULTIPLICATION , *ALGORITHMS , *MATHEMATICAL sequences , *BANDWIDTHS - Abstract
In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, n-by-n matrix multiplication using the conventional O(n³) algorithm, where the input matrices were too huge to Bt in the small, East memory. In 2004 Irony, Toledo, and Tiskin gave a new proof of this result and extended it to the parallel case (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed Ω(#arithinetic_operations/√M), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization. Cholesky factorization, LDLT factorization. QR factorization, the Gram--Schmidt algorithm, and algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth cost), we get lower bounds on the number of messages required to move it (latency cost). We extend our lower bound technique to compositions of linear algebra operations (like Computing powers of a matrix) to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or whether we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph-theoretic problems. We point out recently designed algorithms that attain many of these lower bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
37. COMMUNICATION-OPTIMAL PARALLEL AND SEQUENTIAL CHOLESKY DECOMPOSITION.
- Author
-
BALLARD, GREY, DEMMEL, JAMES, HOLTZ, OLGA, and SCHWARTZ, ODED
- Subjects
- *
MATHEMATICAL decomposition , *SEQUENTIAL analysis , *ALGORITHMS , *NUMERICAL analysis , *MATHEMATICAL models , *BANDWIDTHS , *LINEAR algebra , *FACTORIZATION , *COST , *MEMORY hierarchy (Computer science) - Abstract
Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n3)) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the costs of various Cholesky decomposition implementations to these lower bounds and identify the algorithms and data structures that attain them. In the sequential case, we consider both the two-level and hierarchical memory models. Combined with prior results in [J. Demmel et al., Communication-optimal Parallel and Sequential QR and LU Factorizations, Technical report EECS-2008-89, University of California, Berkeley, CA, 2008], [J. Demmel et al., Implementing Communication-optimal Parallel and Sequential QR and LU Factorizations, SIAM. J. Sci. Comp., submitted], and [J. Demmel, L. Grigori, and H. Xiang, Communication-avoiding Gaussian Elimination, Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, 2008] this gives a set of communication-optimal algorithms for O(n³) implementations of the three basic factorizations of dense linear algebra: LU with pivoting, QR, and Cholesky. But it goes beyond this prior work on sequential LU by optimizing communication for any number of levels of memory hierarchy. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
38. Brief announcement.
- Author
-
Ballard, Grey, Demmel, James, Holtz, Olga, Lipshitz, Benjamin, and Schwartz, Oded
- Published
- 2012
- Full Text
- View/download PDF
39. Shared-memory parallelization of MTTKRP for dense tensors.
- Author
-
Hayashi, Koby, Ballard, Grey, Jiang, Yujie, and Tobia, Michael J.
- Published
- 2018
- Full Text
- View/download PDF
40. Brief announcement.
- Author
-
Ballard, Grey, Demmel, James, and Gearhart, Andrew
- Published
- 2011
- Full Text
- View/download PDF
41. Modeling protein dependency networks using CoCoA.
- Author
-
Ballard, Grey
- Published
- 2006
- Full Text
- View/download PDF
42. Reducing Communication and Computation in Scientific Computing.
- Author
-
Ballard, Grey
- Published
- 2016
43. Computing Tensor Eigenvalues: Theory and Practice.
- Author
-
Ballard, Grey
- Published
- 2011
44. Joint 3D localization and classification of space debris using a multispectral rotating point spread function.
- Author
-
Wang C, Ballard G, Plemmons R, and Prasad S
- Abstract
We consider the problem of joint three-dimensional (3D) localization and material classification of unresolved space debris using a multispectral rotating point spread function (RPSF). The use of RPSF allows one to estimate the 3D locations of point sources from their rotated images acquired by a single 2D sensor array, since the amount of rotation of each source image about its x, y location depends on its axial distance z. Using multispectral images, with one RPSF per spectral band, we are able not only to localize the 3D positions of the space debris but also classify their material composition. We propose a three-stage method for achieving joint localization and classification. In stage 1, we adopt an optimization scheme for localization in which the spectral signature of each material is assumed to be uniform, which significantly improves efficiency and yields better localization results than possible with a single spectral band. In stage 2, we estimate the spectral signature and refine the localization result via an alternating approach. We process classification in the final stage. Both Poisson noise and Gaussian noise models are considered, and the implementation of each is discussed. Numerical tests using multispectral data from NASA show the efficiency of our three-stage approach and illustrate the improvement of point source localization and spectral classification from using multiple bands over a single band.
- Published
- 2019
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.