Novel modifications of parallel Jacobi algorithms

Sanja Singer, Sasa Singer, Vedran Novakovic, Aleksandar Uscumlic, Vedran DunjkoNumer. Algorithms 2012 · DOI

TL;DR

This paper introduces novel parallelization techniques for trigonometric and hyperbolic Jacobi algorithms, aiming to speed up eigenvalue and eigenvector computations for Hermitian matrices. The authors present modifications that improve performance and accuracy, particularly highlighting the superiority of hyperbolic algorithms in practical scenarios.

What Problem Does This Paper Address?

Computing eigenvalues and eigenvectors of Hermitian matrices is a fundamental problem in numerical linear algebra with applications across science and engineering. While the Jacobi algorithm is known for its accuracy, it has historically been considered too slow for practical use. Existing parallelization efforts have improved performance, but there's a continuous need for faster and more accurate algorithms, especially for large-scale problems. This paper addresses the challenge of making Jacobi-type algorithms more efficient and robust for parallel computing environments, focusing on both trigonometric and hyperbolic variants.

Methods

The paper builds upon existing one-sided Jacobi algorithms for computing eigenvalues and eigenvectors of Hermitian matrices. The core contributions lie in:

  • Novel Parallelization Techniques: The authors develop new parallelization strategies for both trigonometric and hyperbolic Jacobi algorithms. These strategies are designed to be applicable to both distributed-memory and shared-memory architectures.
  • Block Algorithms: To enhance parallelism, the paper introduces block-oriented and full block algorithms. These methods process groups of columns (blocks) simultaneously, leading to more efficient use of parallel resources.
  • Pivoting Strategies: New ideas on how to improve the speed of parallel algorithms through smarter pivoting within each cycle are presented. This includes modifications to the modulus pivot strategy for better parallel performance.
  • Factorization Techniques: The paper discusses the use of Hermitian indefinite factorization (Bunch-Parlett) for trigonometric algorithms and Cholesky factorization for hyperbolic algorithms. Special attention is given to specially pivoted Cholesky factorization for indefinite matrices.
  • Hyperbolic vs. Trigonometric: A significant aspect of the work is the comparison and analysis of hyperbolic and trigonometric Jacobi algorithms, with a focus on their practical performance and accuracy.

Datasets

Not discussed in the paper. The authors mention using pseudorandomly generated real symmetric matrices of various orders for numerical testing.

Key Insights and Ideas

  • Hyperbolic Algorithms Outperform: Despite trigonometric algorithms appearing more "natural" theoretically, the numerical testing strongly suggests that hyperbolic Jacobi algorithms are superior in practice, offering better accuracy and speed.
  • Pivoting is Crucial for Speed: The paper emphasizes that effective pivoting strategies are key to significantly increasing the speed of parallel Jacobi algorithms, reducing the number of sweeps required.
  • Block Strategies Enhance Parallelism: The adoption of block-oriented and full block algorithms is essential for exploiting parallelism, allowing for simultaneous processing of multiple column pairs.
  • Accuracy Trade-offs: While Jacobi algorithms are known for their relative accuracy, the paper highlights that repeated accumulation of transformation matrices can lead to error accumulation, particularly in trigonometric algorithms. Hyperbolic algorithms, with their specific factorization approaches, seem to mitigate this better.
  • Communication Patterns Matter: For parallel implementations, the communication patterns, especially in the modulus pivot strategy, are critical for performance. The paper details how these patterns are managed in a ring topology.

Key Results

  • Speedup: The novel parallelization approaches achieve a speedup of approximately 30% over straightforward parallel realizations of existing trigonometric and hyperbolic algorithms.
  • Accuracy: Hyperbolic algorithms demonstrate better accuracy, with computed eigenvectors showing errors around 10⁻¹⁵ or less, compared to 10⁻¹² or less for trigonometric algorithms.
  • Performance Comparison: Figures 4 and 5 show detailed performance comparisons of various trigonometric and hyperbolic algorithms on 64 processes, illustrating the speed advantages of the hyperbolic variants, especially the HFSC and HBSC algorithms.
  • Reduced Sweeps: For large matrices (order 16000), the HFSC algorithm reduced the number of in-process sweeps from 17 to 11 compared to a "classical" HF implementation, contributing to a 30% speedup.

Limitations and Future Work

  • Eigenvector Accuracy Proof: The paper notes that while the relative accuracy of eigenvector computation for hyperbolic Jacobi algorithms has been tested, a formal proof of this accuracy has not yet been extensively established.
  • Stopping Criteria for Block Algorithms: For block-based algorithms that use divide-and-conquer approaches within blocks, determining an optimal stopping criterion remains an open question.
  • Asynchronous Communication: The authors suggest that asynchronous communication patterns might help hide latencies, especially when dealing with indefinite matrices where diagonalization times can vary significantly between blocks.
  • Three-Level Jacobi Algorithms: The paper mentions that further speedups can be achieved by applying sequential blocking within each process, leading to "three-level Jacobi algorithms," which are the subject of a separate paper.
  • Optimal Switching Point: Identifying the optimal switching point between non-blocked and blocked algorithms within a process requires profiling and tuning based on specific hardware and interconnection networks.

Summary updated

BibTeX
@article{singer2012novel,
  author = {Sanja Singer and Sasa Singer and Vedran Novakovic and Aleksandar Uscumlic and Vedran Dunjko},
  title = {{Novel modifications of parallel Jacobi algorithms}},
  journal = {Numer. Algorithms},
  year = {2012},
  doi = {10.1007/s11075-011-9473-6},
}

Loading related content...

Figure