Fetching the paper…

Reading the bibliography…

2016

Parallelepipeds obtaining HBL lower bounds

Demmel, James, Rusciano, Alex

Original
PDF
Post on X

Understand

This work studies the application of the discrete Holder-Brascamp-Lieb (HBL) inequalities to the design of communication optimal algorithms.

In particular, it describes optimal tiling (blocking) strategies for nested loops that lack data dependencies and exhibit linear memory access patterns.
We attain known lower bounds for communication costs by unraveling the relationship between the HBL linear program, its dual, and tile selection.
The methods used are constructive and algorithmic.

Parallelepipeds obtaining HBL lower bounds · Around

Built on

“Finite bounds for Holder-Brascamp-Lieb multilinear inequalities”
Bennett, A. Carbery, M. Christ and T. Tao · 2010
Earlier work this paper cites.
“The Brascamp-Lieb Polyhedron”
Original
S.˜I. Valdimarsson · 2010
Earlier work this paper cites.
“Communication Lower Bounds and Optimal Algorithms for Programs That Reference Arrays Part 1”
M. Christ, J. Demmel, N. Knight, T. Scanlon and K. Yelick · 2013
Earlier work this paper cites.

Similar

“A communication-optimal N-body algorithm for direct interaction”
M. Driscoll, E. Georganas, P. Koanantakool, E. Solomonik and K. Yelick · 2013
Cited alongside, same era.
“A Computation- And Communication-Optimal Parallel Direct 3-Body Algorithm”
P. Koanantakool and K. Yelick · 2014
Cited alongside, same era.
“Uber die von drei Moduln erzeugte Dualgruppe”
Dedekind
Cited in the paper.

Then

“On Holder-Brascamp-Lieb inequalities for torsion-free discrete Abelian groups”
Original
M. Christ, J. Demmel, N. Knight, T. Scanlon and K. Yelick · 2015
Later among the works it cites.
“Algorithmic Aspects of Brascamp-Lieb Inequalities”
Original
A. Garg, L. Gurvits, R. Oliveira and A. Wigderson · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…