Oded Schwartz
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
Oded Schwartz has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Roy Nissim
The Hebrew University of Jerusalem
5 shared publications - Yuval Spiizer
Tel-Aviv University
3 shared publications - Alex Druinsky
Lawrence Berkeley National Laboratory
2 shared publications - Grey Ballard
Department of Computer Science, Wake Forest University, Winston-Salem, NC 27106 USA
2 shared publications - Sivan Toledo
Blavatnik School of Computer Science Tel‐Aviv University Tel Aviv 67798 Israel
2 shared publications - Yoav Moran
Hebrew University of Jerusalem, Jerusalem, Israel
2 shared publications
Latest Publications
- Open Access
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 354-363
Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 354-363
Open AccessTowards Faster Feasible Matrix Multiplication by Trilinear Aggregation
- Open Access
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 297-304
Complex to Rational Fast Matrix Multiplication
- 12 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 297-304
Open AccessComplex to Rational Fast Matrix Multiplication
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 312-316
Brief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 312-316
Open AccessBrief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication
- Open Access
- 26 February 2026
- Published by Springer Nature in Numerische Mathematik
- Vol. 158 (3) , 1151-1185
Alternative Basis matrix multiplication is fast and stable†
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. Particularly, we derive a novel fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs, and achieves an improved asymptotic error bound. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously optimized. We provide high-performance parallel implementations of our algorithms with benchmarks showing that our algorithm is on par with the best in class for speed, and the best in class of 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.
- 26 February 2026
- Published by Springer Nature in Numerische Mathematik
- Vol. 158 (3) , 1151-1185
Open AccessAlternative Basis matrix multiplication is fast and stable†
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. Particularly, we derive a novel fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs, and achieves an improved asymptotic error bound. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously optimized. We provide high-performance parallel implementations of our algorithms with benchmarks showing that our algorithm is on par with the best in class for speed, and the best in class of 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.
- Open Access
Complex to Rational Fast Matrix Multiplication
Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case. Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes.Open AccessComplex to Rational Fast Matrix Multiplication
Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case. Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes. - Open Access
- 8 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 216
Compute-based Fault Tolerance for DNN
- 8 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 216
Open AccessCompute-based Fault Tolerance for DNN
- Open Access
Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, 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 algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice.Open AccessTowards Faster Feasible Matrix Multiplication by Trilinear Aggregation
Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, 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 algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice. - Open Access
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 514-524
Minimizing Processor Count for Fault Tolerant Toom-Cook Algorithms
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 514-524
Open AccessMinimizing Processor Count for Fault Tolerant Toom-Cook Algorithms
- Open Access
- 21 December 2024
- Published by Springer Nature
- p. 120-140
Challenges in Parallel Matrix Chain Multiplication
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) $$ (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.- 21 December 2024
- Published by Springer Nature
- p. 120-140
Open AccessChallenges in Parallel Matrix Chain Multiplication
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) $$ (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.