OHOlga Holtz

Olga Holtz

*This is an algorithmically generated author record based on publicly available information.

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


Olga Holtz has a total of 39 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sparsifying the Operators of Fast Matrix Multiplication Algorithms

    by Gal Beniamini, Nathan Cheng, Olga Holtz, Elaye Karstadt, Oded Schwartz

    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 Access

    Generalized Hurwitz matrices, generalized Euclidean algorithm, and forbidden sectors of the complex plane

    by Olga Holtz, Sergey Khrushchev, Olga Kushel

    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 Access

    Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

    by Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

    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.

  • Szegő’s theorem for matrix orthogonal polynomials

    by Maxim Derevyagin, Olga Holtz, Sergey Khrushchev, Mikhail Tyaglov


  • Open Access

    Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication

    by Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

    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

    Hierarchical zonotopal spaces

    by Olga Holtz, Amos Ron, Zhiqiang Xu

    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

    by Maxim Derevyagin, Olga Holtz, Sergey Khrushchev, Mikhail Tyaglov

    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

    by Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

    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.