A - Z Index | Phone Book | Careers

CACHE Joint Math-CS Institute

As the name suggests, the CACHE Institute is focused on Communication Avoiding and Communication Hiding at Extreme Scales.  The project is a collaboration between researchers at Lawrence Berkeley National Lab (LBNL), Argonne National Lab (ANL), the University of California at Berkeley (UCB), and Colorado State Univeristy (CSU). 

Research Topics

At LBL, we are currently investigating the application of communication avoiding algorithms to geometric multigrid, Krylov Subspace Methods (CG, BiCGSTAB, etc...), and sparse direct solvers based on hierarchically semiseparable matrices.




Samuel Williams, Erin Carson, Mike Lijewski, Nicholas Knight, Ann Almgren, James Demmel, Brian Van Straalen, "s-step Krylov Subspace Methods as Bottom Solvers for Geometric Multigrid", International Parallel and Distributed Processing Symposium (IPDPS), May 2014, doi: 10.1109/IPDPS.2014.119


Christopher D. Krieger, Michelle Mills Strout, Catherine Olschanowsky, Andrew Stone, Stephen Guzik, Xinfeng Gao, Carlo Bertolli, Paul H.J. Kelly, Gihan Mudalige, Brian Van Straalen, Samuel Williams, "Loop Chaining: A Programming Abstraction For Balancing Locality and Parallelism", International Workshop on High-level Parallel Programming Models and Supportive Environments (HIPS), May 2013, doi: 10.1109/IPDPSW.2013.68


Samuel Williams, Dhiraj D. Kalamkar, Amik Singh, Anand M. Deshpande, Brian Van Straalen, Mikhail Smelyanskiy,
Ann Almgren, Pradeep Dubey, John Shalf, Leonid Oliker,
"Implementation and Optimization of miniGMG - a Compact Geometric Multigrid Benchmark", December 2012, LBNL 6676E,

Samuel Williams, Optimization of Geometric Multigrid for Emerging Multi- and Manycore Processors, Supercomputing (SC), November 2012,

S. Williams, D. Kalamkar, A. Singh, A. Deshpande, B. Van Straalen, M. Smelyanskiy, A. Almgren, P. Dubey, J. Shalf, L. Oliker, "Optimization of Geometric Multigrid for Emerging Multi- and Manycore Processors", Supercomputing (SC), November 2012, doi: 10.1109/SC.2012.85

A. Napov, "Conditioning Analysis of Incomplete Cholesky Factorizations with Orthogonal Dropping", 2012, LBNL 5353E,

A. Napov and Y. Notay, "An Algebraic Multigrid Method with Guaranteed Convergence Rate", SIAM J. Sci. Comput., vol.43, pp. A1079-A1109, 2012,


J. Demmel, K. Yelick, M. Anderson, G. Ballard, E. Carson, I. Dumitriu, L. Grigori, M. Hoemmen, O. Holtz, K. Keutzer, N. Knight, J. Langou, M. Mohiyuddin, O. Schwartz, E. Solomonik, S. Williams, Hua Xiang, Rethinking Algorithms for Future Architectures: Communication-Avoiding Algorithms, Hot Chips 23, 2011,

A. Buluç, S. Williams, L. Oliker, J. Demmel, "Reduced-Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication", International Parallel Distributed Processing Symposium (IPDPS), May 2011, doi: 10.1109/IPDPS.2011.73

M. Christen, N. Keen, T. Ligocki, L. Oliker, J. Shalf, B. van Straalen, S. Williams, "Automatic Thread-Level Parallelization in the Chombo AMR Library", LBNL Technical Report, 2011, LBNL 5109E,

A. Napov and Y. Notay, "Smoothing Factor, Order of Prolongation and Actual Multigrid Convergence", Numerische Mathematik , vol.118, pp. 457-483, 2011,

A. Napov and Y. Notay, "Algebraic Analysis of Aggregation-Based Multigrid", Numer. Lin. Alg. Appl., vol.18, pp. 539-564, 2011,

the short version of the paper, winner of the Student Paper competition of 11th Copper Mountain Conference on Iterative Methods