Olga Holtz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Olga Holtz has a total of 39 co-authors. Here are the top co-authors by number of shared publications:
- Grey Ballard
Computer Science Department University of California 94720 Berkeley CA
3 shared publications Ioana Dumitriu
Mathematics Department, University of Washington, Seattle, USA
3 shared publicationsJames Demmel
Mathematics Department and CS Division, University of California, Berkeley, USA
3 shared publications- James Demmel
University of California, Berkeley, Berkeley, CA, USA
3 shared publications - Benjamin Lipshitz
EECS Department UC 94720 Berkeley Berkeley CA
2 shared publications Maxim Derevyagin
Department of Mathematics MA 3-6, Technische Universität Berlin, Strasse des 17. Juni 136, D-10623 Berlin, Germany
2 shared publications
Latest Publications
- Open Access
Sparsifying the Operators of Fast Matrix Multiplication Algorithms
Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity needs to be small. Many sub-cubic algorithms have large leading coefficients, rendering them impractical. Karstadt and Schwartz (SPAA'17, JACM'20) demonstrated how to reduce these coefficients by sparsifying an algorithm's bilinear operator. Unfortunately, the problem of finding optimal sparsifications is NP-Hard. We obtain three new methods to this end, and apply them to existing fast matrix multiplication algorithms, thus improving their leading coefficients. These methods have an exponential worst case running time, but run fast in practice and improve the performance of many fast matrix multiplication algorithms. Two of the methods are guaranteed to produce leading coefficients that, under some assumptions, are optimal.
Open AccessSparsifying the Operators of Fast Matrix Multiplication Algorithms
Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity needs to be small. Many sub-cubic algorithms have large leading coefficients, rendering them impractical. Karstadt and Schwartz (SPAA'17, JACM'20) demonstrated how to reduce these coefficients by sparsifying an algorithm's bilinear operator. Unfortunately, the problem of finding optimal sparsifications is NP-Hard. We obtain three new methods to this end, and apply them to existing fast matrix multiplication algorithms, thus improving their leading coefficients. These methods have an exponential worst case running time, but run fast in practice and improve the performance of many fast matrix multiplication algorithms. Two of the methods are guaranteed to produce leading coefficients that, under some assumptions, are optimal.
- 8 February 2016
- Published by Springer Nature in Computational Methods and Function Theory
- Vol. 16 (3) , 395-431
Generalized Hurwitz Matrices, Generalized Euclidean Algorithm, and Forbidden Sectors of the Complex Plane
- 8 February 2016
- Published by Springer Nature in Computational Methods and Function Theory
- Vol. 16 (3) , 395-431
Generalized Hurwitz Matrices, Generalized Euclidean Algorithm, and Forbidden Sectors of the Complex Plane
- Open Access
Generalized Hurwitz matrices, generalized Euclidean algorithm, and forbidden sectors of the complex plane
Given a polynomial \[ f(x)=a_0x^n+a_1x^{n-1}+\cdots +a_n \] with positive coefficients $a_k$, and a positive integer $M\leq n$, we define a(n infinite) generalized Hurwitz matrix $H_M(f):=(a_{Mj-i})_{i,j}$. We prove that the polynomial $f(z)$ does not vanish in the sector $$ \left\{z\in\mathbb{C}: |\arg (z)| < \frac{\pi}{M}\right\} $$ whenever the matrix $H_M$ is totally nonnegative. This result generalizes the classical Hurwitz' Theorem on stable polynomials ($M=2$), the Aissen-Edrei-Schoenberg-Whitney theorem on polynomials with negative real roots ($M=1$), and the Cowling-Thron theorem ($M=n$). In this connection, we also develop a generalization of the classical Euclidean algorithm, of independent interest per se.Open AccessGeneralized Hurwitz matrices, generalized Euclidean algorithm, and forbidden sectors of the complex plane
Given a polynomial \[ f(x)=a_0x^n+a_1x^{n-1}+\cdots +a_n \] with positive coefficients $a_k$, and a positive integer $M\leq n$, we define a(n infinite) generalized Hurwitz matrix $H_M(f):=(a_{Mj-i})_{i,j}$. We prove that the polynomial $f(z)$ does not vanish in the sector $$ \left\{z\in\mathbb{C}: |\arg (z)| < \frac{\pi}{M}\right\} $$ whenever the matrix $H_M$ is totally nonnegative. This result generalizes the classical Hurwitz' Theorem on stable polynomials ($M=2$), the Aissen-Edrei-Schoenberg-Whitney theorem on polynomials with negative real roots ($M=1$), and the Cowling-Thron theorem ($M=n$). In this connection, we also develop a generalization of the classical Euclidean algorithm, of independent interest per se. - 1 March 2013
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 438 (5) , 2574-2590
Matrices that commute with their derivative. On a letter from Schur to Wielandt
- 1 March 2013
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 438 (5) , 2574-2590
Matrices that commute with their derivative. On a letter from Schur to Wielandt
- Open Access
Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.
Open AccessGraph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.
- 14 May 2012
- Published by Elsevier in Journal of Approximation Theory
- Vol. 164 (9) , 1238-1261
Szegő’s theorem for matrix orthogonal polynomials
- 14 May 2012
- Published by Elsevier in Journal of Approximation Theory
- Vol. 164 (9) , 1238-1261
Szegő’s theorem for matrix orthogonal polynomials
- Open Access
Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
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. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms.
Open AccessCommunication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
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. Benchmarking our implementation on a Cray XT4, we obtain speedups over classical and Strassen-based algorithms ranging from 24% to 184% for a fixed matrix dimension n=94080, where the number of nodes ranges from 49 to 7203. Our parallelization approach generalizes to other fast matrix multiplication algorithms.
- Open Access
- 1 February 2012
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 364 (2) , 745-766
Hierarchical zonotopal spaces
Zonotopal algebra interweaves algebraic, geometric and combinatorial properties of a given linear map . Of basic significance in this theory is the fact that the algebraic structures are derived from the geometry (via a nonlinear procedure known as ``the least map''), and that the statistics of the algebraic structures (e.g., the Hilbert series of various polynomial ideals) are combinatorial, i.e., computable using a simple discrete algorithm known as ``the valuation function''. On the other hand, the theory is somewhat rigid since it deals, for the given , with exactly two pairs, each of which consists of a nested sequence of three ideals: an external ideal (the smallest), a central ideal (the middle), and an internal ideal (the largest).
- 1 February 2012
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 364 (2) , 745-766
Open AccessHierarchical zonotopal spaces
Zonotopal algebra interweaves algebraic, geometric and combinatorial properties of a given linear map . Of basic significance in this theory is the fact that the algebraic structures are derived from the geometry (via a nonlinear procedure known as ``the least map''), and that the statistics of the algebraic structures (e.g., the Hilbert series of various polynomial ideals) are combinatorial, i.e., computable using a simple discrete algorithm known as ``the valuation function''. On the other hand, the theory is somewhat rigid since it deals, for the given , with exactly two pairs, each of which consists of a nested sequence of three ideals: an external ideal (the smallest), a central ideal (the middle), and an internal ideal (the largest).
- Open Access
Szegő's theorem for matrix orthogonal polynomials
We extend some classical theorems in the theory of orthogonal polynomials on the unit circle to the matrix case. In particular, we prove a matrix analogue of Szeg\H{o}'s theorem. As a by-product, we also obtain an elementary proof of the distance formula by Helson and Lowdenslager.
Open AccessSzegő's theorem for matrix orthogonal polynomials
We extend some classical theorems in the theory of orthogonal polynomials on the unit circle to the matrix case. In particular, we prove a matrix analogue of Szeg\H{o}'s theorem. As a by-product, we also obtain an elementary proof of the distance formula by Helson and Lowdenslager.
- Open Access
Communication-optimal Parallel and Sequential Cholesky Decomposition
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(n^3)) 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 [13, 14, 15], this gives a set of communication-optimal algorithms for O(n^3) 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.
Open AccessCommunication-optimal Parallel and Sequential Cholesky Decomposition
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(n^3)) 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 [13, 14, 15], this gives a set of communication-optimal algorithms for O(n^3) 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.