Fast subcubic time matrix multiplication algorithms are asymptotically faster than the classical algorithm, but they are often slower in practice. One obstacle to speed is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication algorithms into equivalent real or rational-coefficient ones.

Matrix multiplication is a fundamental kernel in high-performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices (n > 10100) and thus cannot be used in practice. Of all algorithms applicable to feasible input sizes, Pan’s O(n2.773372) algorithm (1982) is asymptotically the fastest. We obtain an O(n2.773203) algorithm applicable to the same input sizes as Pan’s algorithm. This algorithm is the fastest matrix multiplication algorithm with a base case smaller than 1000. Further, our method obtains the best asymptotic complexity for many small base cases, starting at n0 = 28. We also obtain better exponents (e.g., O(n2.773177)) for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We identify parts of the algorithm that are equivalent to matrix multiplication with smaller base cases, and use the de Groote equivalence to replace these parts in a way that allows further optimization of our algorithms. Finally, we improve the additive complexity of our algorithm by finding a sparse decomposition and reducing the leading coefficient. These algorithms have the potential to outperform existing fast matrix multiplication algorithms in practice.

Toom-Cook-\(k\) (\(2 \le k \in \mathbb{N}\)) is a family of fast algorithms for multiplying long integers using \(O\left(n^{\log_k(2k-1)}\right)\) arithmetic operations, offering asymptotical improvement over the naïve quadratic-time schoolbook approach. Despite this advantage, Toom-Cook algorithms often involve nontrivial divisions, divisions by elements that are not powers of \(2\), which can be both computationally expensive and numerically unstable, especially in cryptography or quantum computing applications. Reducing or eliminating these divisions is therefore of significant theoretical and practical interest.

Sub-cubic time matrix multiplication algorithms can be of practical use, provided that their arithmetic and communication costs are sufficiently small not only in the asymptotic sense, but already for useful input sizes. The alternative basis method has proved to be highly effective for reducing both costs in theory for all known feasible fast matrix multiplication algorithms. It has been tested and combined with other optimization techniques, such as the pebble game, only for Strassen's algorithm, demonstrating significant speedups in practice. The abundance of fast matrix multiplication algorithms and optimization techniques highlights the need for an automatic framework for accelerating the process of obtaining high performance code for them.

Long integer multiplication is a fundamental kernel in various scientific areas, including numerical linear algebra, cryptography, and quantum computing. Toom-Cook-k algorithms run in Θ(nlogk (2k-1)) and are often favored in practice over the Θ (n2) schoolbook algorithm. Faults are a major bottleneck in large-scale computing. The growing size of machines and decreasing operating voltages led to a reduction in the mean time between failures, with modern exascale systems experiencing an error per second. While standard fault-tolerant solutions, such as checkpoint-restart and replication, are straightforward to implement, they incur significant overhead and limit overall system utilization. Algorithm-based fault-tolerant solutions offer a more efficient alternative by leveraging the algorithm's structure, for instance, by incorporating erasure codes into the algorithm. Nissim, Schwartz, and Spiizer (2024) proposed an algorithm-based fault-tolerant solution for the parallel Toom-Cook algorithm. Their solution incurs minor arithmetic and communication costs overheads, but requires a considerable number of additional processors.

Deep neural network (DNN) systems use many GPUs, which can fail---making fault tolerance (FT) essential to avoid cluster restarts. Traditional FT relies on frequent checkpointing, incurring high bandwidth and memory costs. We propose an alternative strategy using GPU redundancy, introducing uniform and heterogeneous encoding approaches. We analyze their costs and recommend usage scenarios, especially for emerging rack-scale AI computers

Alternative basis matrix multiplication algorithms are the fastest matrix multiplication algorithms in practice to date. However, are they numerically stable?We obtain the first numerical error bound for alternative basis matrix multiplication algorithms, demonstrating that their error bounds are asymptotically identical to the standard fast matrix multiplication algorithms, such as Strassen’s. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously and independently optimized. Particularly, we obtain the first fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs and optimal asymptotic error bound, effectively beating the Bini and Lotti (1980) speed-stability trade-off for fast matrix multiplication. We provide high-performance parallel implementations of our algorithms with benchmarks that show our algorithm is on par with the best in class for speed and with the best in class for stability. Finally, we show that diagonal scaling stability improvement techniques for fast matrix multiplication are as effective for alternative basis algorithms, both theoretically and empirically. These findings promote the use of alternative basis matrix multiplication algorithms in practical applications.

Abstract Matrix chain multiplication is widely used in high-performance computing environments. Different parenthesis assignments, which determine the multiplication order, produce the same output but may significantly affect the runtime. Thus, finding the optimal parentheses assignment is crucial. Several algorithms, such as Godbole (1973) and Hu & Shing (1982), have been proposed to address this optimization problem. However, they only focus on minimizing arithmetic operations and disregard inter-processor communication. In many cases, the inter-processor communication cost dominates the total runtime, which makes existing algorithms sub-optimal. Schwartz and Weiss (2019) generalized Godbole’s algorithm to support fast (sub-cubic) matrix multiplication algorithms and demonstrated cases where optimizing arithmetic cost leads to sub-optimal communication cost and vice-versa. We extend their work and show that the runtime of a chain multiplication with a given parentheses assignment additionally depends on processor allocation and available resources. We present a parentheses assignment algorithm that minimizes the total runtime and outperforms previous techniques by a factor of $$\varOmega \left( t^{\frac{1}{3}} \right) $$ Ω t 1 3 (where t is the chain size). Moreover, our algorithm demonstrates up to 7.8x speedup in simulations. To the best of our knowledge, this is the first study that discusses resource allocation in the context of matrix chain multiplication.

Exascale machines have a small mean time between failures, necessitating fault tolerance. Out-of-the-box fault-tolerant solutions, such as checkpoint-restart and replication, apply to any algorithm but incur significant overhead costs. Long integer multiplication is a fundamental kernel in numerical linear algebra and cryptography. The naive, schoolbook multiplication algorithm runs in Θ(n2) while Toom-Cook algorithms runs in Θ(nlogk (2k-1)) for 2 ≤ k. We obtain the first efficient fault-tolerant parallel Toom-Cook algorithm. While asymptotically faster FFT-based algorithms exist, Toom-Cook algorithms are often favored in practice on small scale and on supercomputers. Our algorithm enables fault tolerance with negligible overhead costs. Compared to existing, general-purpose, fault-tolerant solutions, our algorithm reduces the arithmetic and communication (bandwidth) overhead costs by a factor of Θ(P/(2k-1)) (where P is the number of processors). To this end, we adapt the fault-tolerant BFS-DFS method of Birnbaum et al. (2020) for fast matrix multiplication and combine it with a coding strategy tailored for Toom-Cook. This eliminates the need for recomputations, resulting in a much faster algorithm.

Pan’s four decades old fast matrix multiplication algorithms have the lowest asymptotic complexity of all currently known algorithms applicable to matrices of feasible dimensions. However, the large coefficients in the arithmetic cost of these algorithms make them impractical. We reduce these coefficients by , in some cases to a value of 2, the same leading coefficient as the classical, cubic time algorithm. For this purpose, we utilize fast recursive transformations with sparsification of the linear operators of Pan’s algorithms. Existing decomposition methods cannot be applied to Pan’s algorithms due to their large base cases. We describe two new methods for finding such decompositions, by utilizing the underlying symmetries of the algorithms, and the linear transformations within the algorithms. With these tools, we obtain algorithms with the same asymptotic complexity as Pan’s algorithms, but with small leading coefficients, often the same as that of the cubic time algorithm. In practice, these new algorithms have the potential to outperform the fastest currently known matrix multiplication algorithms on feasible sized inputs. Matched against known lower bounds, we show that our results are optimal or close to being optimal.

Fast parallel and sequential matrix multiplication algorithms switch to the cubic time classical algorithm on small sub-blocks as the classical algorithm requires fewer operations on small blocks. We obtain a new algorithm that can outperform the classical one, even on small blocks, by trading multiplications with additions. This algorithm contradicts the common belief that the classical algorithm is the fastest algorithm for small blocks. To this end, we introduce commutative algorithms that generalize Winograd's folding technique (1968) and combine it with fast matrix multiplication algorithms. Thus, when a single scalar multiplication requires ρ times more clock cycles than an addition (e.g., for 16-bit integers on Intel's Skylake microarchitecture, ρ is between 1.5 and 5), our technique reduces the computation cost of multiplying the small sub-blocks by a factor of ρ + 3 over 2(ρ + 1) compared to using the classical algorithm, at the price of a low order term communication cost overhead both in the sequential and the parallel cases, thus reducing the total runtime of the algorithm. Our technique also reduces the energy cost of the algorithm. The ρ values for energy costs are typically larger than the ρ values for arithmetic costs. For example, we obtain an algorithm for multiplying 2 x 2 blocks using only four multiplications. This algorithm seemingly contradicts the lower bound of Winograd (1971) on multiplying 2 x 2 matrices. However, we obtain this algorithm by bypassing the implicit assumptions of the lower bound. We provide a new lower bound matching our algorithm for 2 x 2 block multiplication, thus showing our technique is optimal.

Strassen’s algorithm (1969) was the first sub-cubic matrix multiplication algorithm. Winograd (1971) improved the leading coefficient of its complexity from 6 to 7. There have been many subsequent asymptotic improvements. Unfortunately, most of these have the disadvantage of very large, often gigantic, hidden constants. Consequently, Strassen-Winograd’s O ( n log 2 7 ) algorithm often outperforms other fast matrix multiplication algorithms for all feasible matrix dimensions. The leading coefficient of Strassen-Winograd’s algorithm has been generally believed to be optimal for matrix multiplication algorithms with a 2 × 2 base case, due to the lower bounds by Probert (1976) and Bshouty (1995). Surprisingly, we obtain a faster matrix multiplication algorithm, with the same base case size and asymptotic complexity as Strassen-Winograd’s algorithm, but with the leading coefficient reduced from 6 to 5. To this end, we extend Bodrato’s (2010) method for matrix squaring, and transform matrices to an alternative basis. We also prove a generalization of Probert’s and Bshouty’s lower bounds that holds under change of basis, showing that for matrix multiplication algorithms with a 2 × 2 base case, the leading coefficient of our algorithm cannot be further reduced, and is therefore optimal. We apply our method to other fast matrix multiplication algorithms, improving their arithmetic and communication costs by significant constant factors.

Communication costs, between processors and across the memory hierarchy, often dominate the runtime of algorithms. Can we trade these costs for recomputations? Most algorithms do not utilize recomputation for this end, and most communication cost lower bounds assume no recomputation, hence do not address this fundamental question. Recently, Bilardi and De Stefani (2017), and Bilardi, Scquizzato, and Silvestri (2018) showed that recomputations cannot reduce communication costs in Strassen's fast matrix multiplication and in fast Fourier transform. We extend the former bound and show that recomputations cannot reduce communication costs for a few other fast matrix multiplication algorithms.

The Matrix Chain Ordering Problem is a well studied optimization problem, aiming at finding optimal parentheses assignment for minimizing the number of arithmetic operations required when computing a chain of matrix multiplications. Existing algorithms include the O(N3) dynamic programming of Godbole (1973) and the faster O(N log N) algorithm of Hu and Shing (1982). We show that both may result in suboptimal parentheses assignment on modern machines as they do not take into account inter-processor communication costs that often dominate the running time. Further, the optimal solution may change when using fast matrix multiplication algorithms. We show that the O(N3) dynamic-programing algorithm easily adapts to provide optimal solutions for modern matrix multiplication algorithms, and obtain an adaption of the O(N log N) algorithm that guarantees a constant approximation.

Fast matrix multiplication algorithms are of practical use only if the leading coefficient of their arithmetic complexity is sufficiently small. Many algorithms with low asymptotic cost have large leading coefficients, and are thus impractical. Karstadt and Schwartz have recently demonstrated a technique that reduces the leading coefficient by introducing fast O(n2 łog n) basis transformations, applied to the input and output matrices. We generalize their technique, by allowing larger bases for the transformations while maintaining low overhead. Thus we accelerate several matrix multiplication algorithms, beyond what is known to be possible using the previous technique. Of particular interest are a few new sub-cubic algorithms with leading coefficient 2, matching that of classical matrix multiplication. For example, we obtain an algorithm with arithmetic complexity of 2nłog323 + o( nłog323) compared to 2n3 - n2 of the classical algorithm. Such new algorithms can outperform previous ones (classical included) even on relatively small matrices. We obtain lower bounds matching the coefficient of several of our algorithms, proving them to be optimal.

The matrix chain ordering problem aims to reduce the number of arithmetic operations required for evaluating the product of $N$ matrices. Using a dynamic programming algorithm this problem can be solved in $O(N^3)$ time. Hu and Shing obtained a sophisticated algorithm that solves the problem in $O ( N\log{N} )$ [ SIAM J. Comput., 11 (1982), pp. 362--373]. Unfortunately, as we show here, the correctness proof of their algorithm is wrong. This flaw affects another algorithm for the same problem, by Wang, Zhu, and Tian (2013), and algorithms for many other problems that use chain matrix multiplication as a building block. We present an alternative proof for the correctness of the first two algorithms and show that a third algorithm by Nimbark, Gohel, and Doshi (2011) is beyond repair.

Strassen's algorithm (1969) was the first sub-cubic matrix multiplication algorithm. Winograd (1971) improved its complexity by a constant factor. Many asymptotic improvements followed. Unfortunately, most of them have done so at the cost of very large, often gigantic, hidden constants. Consequently, Strassen-Winograd's O(nlog27) algorithm often outperforms other matrix multiplication algorithms for all feasible matrix dimensions. The leading coefficient of Strassen-Winograd's algorithm was believed to be optimal for matrix multiplication algorithms with 2x2 base case, due to a lower bound of Probert (1976).

Communication, i.e., moving data between levels of a memory hierarchy or between processors over a network, is much more expensive (in time or energy) than arithmetic. There has thus been a recent focus on designing algorithms that minimize communication and, when possible, attain lower bounds on the total number of reads and writes. However, most previous work does not distinguish between the costs of reads and writes. Writes can be much more expensive than reads in some current and emerging storage devices such as nonvolatile memories. This motivates us to ask whether there are lower bounds on the number of writes that certain algorithms must perform, and whether these bounds are asymptotically smaller than bounds on the sum of reads and writes together. When these smaller lower bounds exist, we then ask when they are attainable, we call such algorithms "write-avoiding" (WA), to distinguish them from "communication-avoiding" (CA) algorithms, which only minimize the sum of reads and writes. We identify a number of cases in linear algebra and direct N-body methods where known CA algorithms are also WA (some are and some aren't). We also identify classes of algorithms, including Strassen's matrix multiplication, Cooley-Tukey FFT, and cache oblivious algorithms for classical linear algebra, where a WA algorithm cannot exist: the number of writes is unavoidably within a constant factor of the total number of reads and writes. We explore the interaction of WA algorithms with cache replacement policies and argue that the Least Recently Used policy works well with the WA algorithms in this paper. We provide empirical hardware counter measurements from Intel's Nehalem-EX microarchitecture to validate our theory. In the parallel case, for classical linear algebra, we show that it is impossible to attain lower bounds both on interprocessor communication and on writes to local memory, but either one is attainable by itself. Finally, we discuss WA algorithms for sparse iterative linear algebra.

The performance of parallel algorithms for sparse matrix-matrix multiplication is typically determined by the amount of interprocessor communication performed, which in turn depends on the nonzero structure of the input matrices. In this paper, we characterize the communication cost of a sparse matrix-matrix multiplication algorithm in terms of the size of a cut of an associated hypergraph that encodes the computation for a given input nonzero structure. Obtaining an optimal algorithm corresponds to solving a hypergraph partitioning problem. Our hypergraph model generalizes several existing models for sparse matrix-vector multiplication, and we can leverage hypergraph partitioners developed for that computation to improve application-specific algorithms for multiplying sparse matrices.

We apply a novel technique based on path routings to obtain optimal I/O-complexity lower bounds for all Strassen-like fast matrix multiplication algorithms computed in serial or in parallel, assuming no reuse of nontrivial intermediate linear combinations. Given fast memory of size M, we prove an I/O-complexity lower bound of Ω((n/√M}ω0 • M) for any Strassen-like matrix multiplication algorithm applied to n x n matrices of arithmetic complexity Θ(nω0) with ω0<3 under this assumption. This generalizes an approach by Ballard, Demmel, Holtz, and Schwartz that provides a tight lower bound for Strassen's matrix multiplication algorithm but which does not apply to algorithms with disconnected encoding or decoding components of the underlying computation graph or algorithms with multiply copied values. We overcome these challenges via a new graph-theoretical approach for proving I/O-complexity lower bounds without the use of edge expansions.

Factorization of a dense symmetric indefinite matrix is a key computational kernel in many scientific and engineering simulations. However, there is no scalable factorization algorithm that takes advantage of the symmetry and guarantees numerical stability through pivoting at the same time. This is because such an algorithm exhibits many of the fundamental challenges in parallel programming like irregular data accesses and irregular task dependencies. In this paper, we address these challenges in a tiled implementation of a blocked Aasen's algorithm using a dynamic scheduler. To fully exploit the limited parallelism in this left-looking algorithm, we study several performance enhancing techniques; e.g., parallel reduction to update a panel, tall-skinny LU factorization algorithms to factorize the panel, and a parallel implementation of symmetric pivoting. Our performance results on up to 48 AMD Opteron processors demonstrate that our implementation obtains speedups of up to 2.8 over MKL, while losing only one or two digits in the computed residual norms.

Abstract—Communication-optimal algorithms are known for square matrix multiplication. Here, we obtain the first communication-optimal algorithm for all dimensions of rectangular matrices. Combining the dimension-splitting technique of Frigo, Leiserson, Prokop and Ramachandran (1999) with the recursive BFS/DFS approach of Ballard, Demmel, Holtz, Lipshitz and Schwartz (2012) allows for a communication-optimal as well as cache- and network-oblivious algorithm. Moreover, the implementation is simple: approximately 50 lines of code for the shared-memory version. Since the new algorithm minimizes communication across the network, between NUMA domains, and between levels of cache, it performs well in practice on both shared- and distributed-memory machines. We show significant speedups over existing parallel linear algebra libraries both on a 32-core shared-memory machine and on a distributed-memory supercomputer. Index Terms—communication-avoiding algorithms; linear algebra; matrix multiplication I.

Energy efficiency of computing devices has become a dominant area of research interest in recent years. Most previous work has focused on architectural techniques to improve power and energy efficiency; only a few consider saving energy at the algorithmic level. We prove that a region of perfect strong scaling in energy exists for matrix multiplication (classical and Strassen) and the direct n-body problem via the use of algorithms that use all available memory to replicate data. This means that we can increase the number of processors by some factor and decrease the runtime (both computation and communication) by the same factor, without changing the total energy use.

Parallel algorithms for sparse matrix-matrix multiplication typically spend most of their time on inter-processor communication rather than on computation, and hardware trends predict the relative cost of communication will only increase. Thus, sparse matrix multiplication algorithms must minimize communication costs in order to scale to large processor counts.

High performance for numerical linear algebra often comes at the expense of stability. Computing the LU decomposition of a matrix via Gaussian Elimination can be organized so that the computation involves regular and efficient data access. However, maintaining numerical stability via partial pivoting involves row interchanges that lead to inefficient data access patterns. To optimize communication efficiency throughout the memory hierarchy we confront two seemingly contradictory requirements: partial pivoting is efficient with column-major layout, whereas a block-recursive layout is optimal for the rest of the computation. We resolve this by introducing a shape morphing procedure that dynamically matches the layout to the computation throughout the algorithm, and show that Gaussian Elimination with partial pivoting can be performed in a communication efficient and cache-oblivious way. Our technique extends to QR decomposition, where computing Householder vectors prefers a different data layout than the rest of the computation.

A fundamental task in wireless communication is channel estimation: Compute the channel parameters a signal undergoes while traveling from a transmitter to a receiver. In the case of delay-Doppler channel, i.e., a signal undergoes only delay and Doppler shifts, a widely used method to compute the delay-Doppler parameters is the matched filter algorithm. It uses a pseudo-random sequence of length N, and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is O(N2logN). In this paper we introduce a novel approach of designing sequences that allow faster channel estimation. Using group representation techniques we construct sequences, which enable us to introduce a new algorithm, called the flag method, that significantly improves the matched filter algorithm. The flag method finds m delay-Doppler parameters in O(mNlogN) operations. We discuss applications of the flag method to GPS, and radar systems.

A fundamental task in wireless communication is channel estimation: Compute the channel parameters a signal undergoes while traveling from a transmitter to a receiver. In the case of delay-Doppler channel, a widely used method is the matched filter algorithm. It uses a pseudo-random waveform of length N, and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is O(N2log(N)). In this paper we introduce a novel approach of designing waveforms that allow faster channel estimation. Using group representation techniques we construct waveforms, which enable us to introduce a new algorithm, called the flag method, that significantly improves the matched filter algorithm. The flag method finds the channel parameters in O(m · N log(N)) operations, for channel of sparsity of order m. We discuss applications of the flag method to GPS, and radar system as well.

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.

A parallel algorithm has perfect strong scaling if its running time on $P$ processors is linear in $1/P$, including all communication costs. Distributed-memory parallel algorithms for matrix multiplication with perfect strong scaling have only recently been found. One is based on classical matrix multiplication (Solomonik and Demmel, 2011), and one is based on Strassen's fast matrix multiplication (Ballard, Demmel, Holtz, Lipshitz, and Schwartz, 2012). Both algorithms scale perfectly, but only up to some number of processors where the inter-processor communication no longer scales. We obtain a memory-independent communication cost lower bound on classical and Strassen-based distributed-memory matrix multiplication algorithms. These bounds imply that no classical or Strassen-based parallel matrix multiplication algorithm can strongly scale perfectly beyond the ranges already attained by the two parallel algorithms mentioned above. The memory-independent bounds and the strong scaling bounds generalize to other algorithms.

Parallel matrix multiplication is one of the most studied fundamental problems in distributed and high performance computing. We obtain a new parallel algorithm that is based on Strassen's fast matrix multiplication and minimizes communication. The algorithm outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based, both asymptotically and in practice. A critical bottleneck in parallelizing Strassen's algorithm is the communication between the processors. Ballard, Demmel, Holtz, and Schwartz (SPAA '11) prove lower bounds on these communication costs, using expansion properties of the underlying computation graph. Our algorithm matches these lower bounds, and so is communication-optimal. It exhibits perfect strong scaling within the maximum possible range.

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.

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. For sequential algorithms these bounds are attainable and so optimal.

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, which is used for solving dense symmetric positive definite linear systems. Second, we compare the cost of various Cholesky implementations to this lower bound, and draw the following conclusions:

We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.