English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we consider two fundamental symmetric kernels in linearalgebra: the Cholesky factorization and the symmetric rank-$k$ update (SYRK),with the classical three nested loops algorithms for these kernels. Inaddition, we consider a machine model with a fast memory of size $S$ and anunbounded slow memory. In this model, all computations must be performed onoperands in fast memory, and the goal is to minimize the amount ofcommunication between slow and fast memories. As the set of computations isfixed by the choice of the algorithm, only the ordering of the computations(the schedule) directly influences the volume of communications.We prove lowerbounds of $\frac{1}{3\sqrt{2}}\frac{N^3}{\sqrt{S}}$ for the communicationvolume of the Cholesky factorization of an $N\times N$ symmetric positivedefinite matrix, and of $\frac{1}{\sqrt{2}}\frac{N^2M}{\sqrt{S}}$ for the SYRKcomputation of $\mat{A}\cdot\transpose{\mat{A}}$, where $\mathbf{A}$ is an$N\times M$ matrix. Both bounds improve the best known lower bounds from theliterature by a factor $\sqrt{2}$.In addition, we present two out-of-core,sequential algorithms with matching communication volume: \TBS for SYRK, with avolume of $\frac{1}{\sqrt{2}}\frac{N^2M}{\sqrt{S}} + \bigo{NM\log N}$, and \LBCfor Cholesky, with a volume of $\frac{1}{3\sqrt{2}}\frac{N^3}{\sqrt{S}} +\bigo{N^{5/2}}$. Both algorithms improve over the best known algorithms fromthe literature by a factor $\sqrt{2}$, and prove that the leading terms in ourlower bounds cannot be improved further. This work shows that the operationalintensity of symmetric kernels like SYRK or Cholesky is intrinsically higher(by a factor $\sqrt{2}$) than that of corresponding non-symmetric kernels (GEMMand LU factorization).

I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels