Oded Schwartz - homepage

Oded Schwartz

My Picture Rothberg A405
+972(2)5494576
odedsc@cs.huji.ac.il


I am an associate professor at the School of Engineering and Computer Science , the Hebrew University. My current research interests include parallel computing, algorithms for supercomputers, scientific computing, algorithmic linear algebra, high performance computing, and accelerating algorithms by reducing communication costs.


Honors & Awards

  • 2014 Communication of the ACM Research Highlights Recognition, for the paper
    Graph Expansion and Communication Costs of Fast Matrix Multiplication with Grey Ballard, James Demmel, and Olga Holtz.
  • 2013 IEEE International Parallel & Distributed Processing Symposium Best Paper Award, for
    Implementing a Blocked Aasen's Algorithm with a Dynamic Scheduler on Multicore Architectures with
    Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Sivan Toledo, and Ichitaro Yamazaki.
  • 2012 SIAG/Linear Algebra Best Paper Prize (for the years 2009-2011), for
    Minimizing Communication in Numerical Linear Algebra with Grey Ballard, James Demmel, and Olga Holtz.
    Awarded at SIAM Conference on Applied Linear Algebra.
  • 2011 ACM Symposium on Parallelism in Algorithms and Architectures Best Paper Award, for
    Graph Expansion and Communication Costs of Fast Matrix Multiplication with Grey Ballard, James Demmel, and Olga Holtz.
  • 2001 - 2006 The School of Computer Science scholarship, Tel-Aviv University.
  • 2002 - 2006 The Vatat Scholarship for higher technology.
  • 2003 The Paul Viderman prize for Outstanding Teaching, Tel-Aviv University.
  • 2002 The Yeshayahu Lavi award for excellence in M.Sc. studies, Tel-Aviv University.
  • 2002 MSc summa cum laude, Tel-Aviv University.
  • 1995 Full Scholarship, The Adi Lautman Interdisciplinary program for outstanding students, Tel-Aviv University.

    • Students

    Noam Birnbaum, M.Sc. student
    Nitzan Gado, M.Sc. student
    Elaye Karstadt, Ph.D. student
    Roy Nissim, M.Sc. student
    Yishai Oltchik, M.Sc. student
    Reut Shabo, M.Sc. student
    Elad Weiss, M.Sc. student


    Recent Professional Activities

    SPAA'18 PC, SIAM CSC'18 PC, SIAM PP'18 (mini symp. organizer), IPDPS'17 PC, HiPC'16 PC, SIAM-PP'16 (mini symp. organizer), IPDPS'15 PC, HiPC'15 PC, SIAM-ALA'15 (mini symp. organizer), SPAA'14 PC, SIAM-PP'14 (mini symp. organizer).

    Teaching

  • Hebrew University:
    2015-2018, Advanced parallel computing (67833)
    2017-2018, Reading course (67859)
    2016-2018, Computational models, computability, and complexity (67521)
    2015-2018, Algorithms for supercomputers seminar (67895)
    2014-2018, Algorithms for supercomputers workshop (67896)
  • UC-Berkeley:
    Scientific Computing and Matrix Computations Seminar, Spring 2013, with James Demmel (Math 290, Section 25, CS 298, Section 6).
    Scientific Computing and Matrix Computations Seminar, Fall 2012, with James Demmel (Math 290, Section 25, CS 298, Section 6).
    Communication-Avoiding Algorithms, Fall 2011, with James Demmel (CS294-76).
  • Tel-Aviv University: Introduction to Algorithms and Data Structures (lectures and TA), Computational Complexity (lectures and TA), Advanced Computational Complexity (lectures and TA), Computational Neuroscience (TA), Analysis of Boolean Functions (TA).
  • Taught similar courses at The Academic College of Tel-Aviv-Yaffo and at The Open University.
  • Received the Paul Viderman Prize for Outstanding Teaching (at Tel-Aviv University).

    • Publications

    (bibtex)

    Journals

  • High-Performance Algorithms for Computing the Sign Function of Triangular Matrices
    Vadim Stotland, Oded Schwartz, and Sivan Toledo.
    Numerical Linear Algebra with Applications (NLAA), in press, 2017.

  • Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication
    Grey Ballard, Alex Druinsky, Nick Knight, and Oded Schwartz
    ACM Transactions on Parallel Computing (TOPC), 2016.

  • Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
    Ariful Azad, Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Oded Schwartz, Sivan Toledo, and Samuel Williams.
    SIAM Journal on Scientific Computing (SISC), 38(6), pp. C624–C651, 2016.

  • Improving the numerical stability of fast matrix multiplication algorithms
    Grey Ballard, Austin Benson, Alex Druinsky, Ben Lipshitz, and Oded Schwartz
    SIAM Journal on Matrix Analysis and Applications (SIMAX), 37(4), pp. 1382-1418, 2016.

  • Communication-avoiding symmetric-indefinite factorization.
    Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Oded Schwartz, Sivan Toledo, and Ichitaro Yamazaki
    SIAM Journal on Matrix Analysis and Applications (SIMAX). 35(4): 1364-1406, 2014.

  • Numerical Linear Algebra: Communication Costs
    Grey Ballard, Erin Carson, James Demmel, Mark Hoemmen, Nick Knight, and Oded Schwartz.
    Invited to Acta Numerica. Cambridge University Press, 23, 1-155, 2014.

  • Communication Costs of Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Invited to Research Highlights section of the Communications of the ACM, 2014.

  • Delay-Doppler Channel Estimation in Almost Linear Time
    Alex Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, and Oded Schwartz
    IEEE Transactions on Information Theory, 2013.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Journal of the ACM (JACM), 59(6) Article 32:1-23, 2012.

  • Minimizing Communication in Numerical Linear Algebra
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    SIAM Journal on Matrix Analysis and Applications (SIMAX). 32(3): 866-901, 2011.
    Awarded the 2012 SIAG/LA Best Paper Prize for the years 2009-2011.

  • Colorful Strips
    Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian.
    Invited to Special Issue of Graphs and Combinatorics 27(3): 327-339, Springer, 2011.

  • Communication-Optimal Parallel and Sequential Cholesky Decomposition
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    SIAM Journal on Scientific Computing (SISC), 32(6): 3495-3523, 2010.

  • Quantum Expanders: Motivation and Constructions
    Avi Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.
    Theory of Computing, 6(1): 47-79, 2010.

  • Cooperative TSP
    Adi Avidor, Amitai Armon, and Oded Schwartz.
    Theoretical Computer Science, 411: 2847-2863, 2010.

  • An Elementary Construction of Constant Degree Expanders
    Noga Alon, Oded Schwartz, and Asaf Shapira.
    Combinatorics, Probability and Computing, 17: 319-327, 2008.

  • On the Complexity of Approximating k-Set-Packing
    Elad Hazan, Muli Safra, and Oded Schwartz.
    Computational Complexity, 15(1): 20-39, 2006.

  • On the Complexity of Approximating TSP with Neighborhoods and Related Problems
    Muli Safra and Oded Schwartz.
    Computational Complexity, 14(4): 281-307, 2006.

    • Refereed Conference Articles

  • Fault Tolerant Resource Efficient Matrix Multiplication
    Noam Birnbaum and Oded Schwartz.
    In CSC'18: Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, 2018.
    A longer version of this paper appears here.

  • Efficient Evaluation of Matrix Polynomials
    Niv Hoffman, Oded Schwartz, and Sivan Toledo.
    In PPAM'17: International Conference on Parallel Processing and Applied Mathematics, 2017.

  • Matrix Multiplication, a Little Faster
    Elaye Karstadt and Oded Schwartz.
    In SPAA'17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017.
    A poster with these results won the Hebrew University of Jerusalem Faculty of Science Best Poster Award, 2017

  • Network Topologies and Inevitable Contention
    Grey Ballard, James Demmel, Andrew Gearhart, Ben Lipshitz, Yishai Oltchik, Oded Schwartz, and Sivan Toledo.
    In COMHPC'16: Proceedings of the Communication Optimizations in HPC Workshop at SuperComputing, 2016.

  • Write Avoiding Algorithms
    Erin Carson, James Demmel, Laura Grigori, Nick Knight, Penporn Koanantakool, Oded Schwartz, and Harsha Simhardi.
    In IPDPS'16: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, 2016.

  • Brief announcement: Hypergraph partitioning for parallel sparse matrix-matrix multiplication
    Grey Ballard, Alex Druinsky, Nick Knight, and Oded Schwartz
    In SPAA'15: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 86-88, 2015.

  • Matrix Multiplication I/O-Complexity by Path Routing
    Jacob Scott, Olga Holtz, and Oded Schwartz
    In SPAA'15: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 35-45, 2015.

  • Communication Efficient Gaussian Elimination with Partial Pivoting using a Shape Morphing Data Layout
    Grey Ballard, James Demmel, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In SPAA'13: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 232-241, 2013.

  • Communication Optimal Parallel Multiplication of Sparse Random Matrices
    Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In SPAA'13: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 222-231, 2013.

  • Implementing a Blocked Aasen's Algorithm with a Dynamic Scheduler on Multicore Architectures
    Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Oded Schwartz, Sivan Toledo, and Ichitaro Yamazaki
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, 2013.
    (IPDPS'13 Best Paper Award).

  • Perfect Strong Scaling Using No Additional Energy
    James Demmel, Andrew Gearhart, Ben Lipshitz, and Oded Schwartz
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, 2013.

  • Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication
    James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, 2013.

  • Communication-Avoiding Parallel Strassen: Implementation and Performance
    Grey Ballard, James Demmel, Ben Lipshitz, and Oded Schwartz
    In SuperComputing'12: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2012.

  • Delay-Doppler Channel Estimation in Almost Linear Complexity
    Alex Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, and Oded Schwartz
    In ISIT'12: Proceedings of the IEEE International Symposium on Information Theory, pp. 2386-2390, 2012.

  • Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In SPAA'12: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 193-204, 2012.

  • Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds (Brief Announcement)
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In SPAA'12: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 77-79, 2012.

  • Graph Expansion and Communication Costs of Fast Rectangular Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In MedAlg'12: Proceedings of the 1st Mediterranean Conference on Algorithms, pp. 13-36, 2012.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    In SPAA'11: Proceedings of the 23th ACM Symposium on Parallelism in Algorithms and Architectures`, Pittsburgh, Pennsylvania, USA, pp. 1-12, 2011.
    (SPAA'11 Best Paper Award).

  • Colorful Strips
    Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian.
    In LATIN'10: Proceedings of the 9th Latin American conference on Theoretical Informatics, Oaxaca, Mexico, pp. 2-13, 2010.

  • Communication-Optimal Parallel and Sequential Cholesky Decomposition
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    In SPAA'09: Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures, pp. 245-252, Calgary, Canada, 2009.

  • Quantum Expanders: Motivation and Constructions
    Avi Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.
    In CCC'08: Proceedings of the 23rd IEEE Conference on Computational Complexity, pp. 292-303, College Park, Maryland, USA, 2008.

  • An Elementary Construction of Constant Degree Expanders
    Noga Alon, Oded Schwartz, and Asaf Shapira.
    In SODA'07: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319-327 , New Orleans, Louisiana, USA, 2007.

  • Cooperative TSP
    Adi Avidor, Amitai Armon, and Oded Schwartz.
    In ESA'06: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 40-51, Zurich, Switzerland, 2006.

  • On the Complexity of Approximating k-Dimensional-Matching
    Elad Hazan, Muli Safra, and Oded Schwartz.
    In APPROX'03: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 59-70, Princeton, NY, USA, 2003.

  • On the Complexity of Approximating TSP with Neighborhoods and Related Problems
    Muli Safra and Oded Schwartz.
    In ESA'03: Proceedings of the 11th Annual European Symposium on Algorithms, pp. 446-458, Budapest, Hungary, 2003.

    • Theses

  • Expansion and Approximability
    Advisors: Muli Safra and Amnon Ta-Shma.
    PhD thesis, Tel-Aviv University, June, 2008.

  • On the Hardness of Approximating TSP with Neighborhoods, Group TSP and Group Steiner Tree
    Advisor: Muli Safra.
    MSc thesis, Tel-Aviv University, 2002.

    • Posters

  • Beating MKL and ScaLapack at Rectangular Matrix Multiplication Using the BFS/DFS Approach
    James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    SuperComputing'12: International Conference for High Performance Computing Networking, Storage and Analysis, Salt Lake City, Utah, USA, 2012.
    A preliminary version of this poster appeared in Parlab retreat, 2012 (next item).

  • Towards Automated Parallelization of Recursive Algorithms in SEJITS: Beating MKL's Matrix Multiplication Using the BFS/DFS Approach
    James Demmel, David Eliahu, Armando Fox, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    Parlab retreat, 2012.

  • Communication-Avoiding Parallel Strassen: Implementation and Performance
    Grey Ballard, James Demmel, Ben Lipshitz, and Oded Schwartz
    Parlab retreat, 2012.

  • Communication Costs of Schönhage-Strassen Fast Integer Multiplication
    Derrick Coetzee, James Demmel, and Oded Schwartz.
    Parlab retreat, 2011.

  • Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Ben Lipshitz, and Oded Schwartz.
    Parlab retreat, 2011.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Parlab retreat, 2011.