Skip to navigation Skip to content
Careers | Phone Book | A - Z Index
Performance and Algorithms Research

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 University (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, Mike Lijewski, Ann Almgren, Brian Van Straalen, Erin Carson, Nicholas Knight, James Demmel, "s-step Krylov subspace methods as bottom solvers for geometric multigrid", Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, January 2014, 1149--1158, 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, Sam Williams, "Loop chaining: A programming abstraction for balancing locality and parallelism", Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, May 2013, 375--384, 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", Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (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,

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