OSOded Schwartz

Oded Schwartz

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Oded Schwartz has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • 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.

  • Open Access

    Delay-Doppler Channel Estimation with Almost Linear Complexity

    by Alexander Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, Oded Schwartz

    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 sequence of length N, and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is O(N^{2}log(N)). 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 the channel parameters in O(mNlog(N)) operations, for channel of sparsity m. We discuss applications of the flag method to GPS, radar system, and mobile communication as well.

  • 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

    Computing the Matched Filter in Linear Time

    by Alexander Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, Oded Schwartz

    A fundamental problem in wireless communication is the time-frequency shift (TFS) problem: Find the time-frequency shift of a signal in a noisy environment. The shift is the result of time asynchronization of a sender with a receiver, and of non-zero speed of a sender with respect to a receiver. A classical solution of a discrete analog of the TFS problem is called the matched filter algorithm. It uses a pseudo-random waveform S(t) of the length p, and its arithmetic complexity is O(p^{2} \cdot log (p)), using fast Fourier transform. In these notes we introduce a novel approach of designing new waveforms that allow faster matched filter algorithm. We use techniques from group representation theory to design waveforms S(t), which enable us to introduce two fast matched filter (FMF) algorithms, called the flag algorithm, and the cross algorithm. These methods solve the TFS problem in O(p\cdot log (p)) operations. We discuss applications of the algorithms to mobile communication, GPS, and radar.