(CLOSED) EXPRESS: Randomized Algorithms for Extreme Scale Science (DE-FOA-0002497)

SUMMARY
The DOE SC program in Advanced Scientific Computing Research (ASCR) hereby announces its interest in research applications to explore potentially high-impact approaches in the development and use of randomized algorithms for scientific computing and extreme-scale science.

SUPPLEMENTARY INFORMATION

Randomized algorithms are transforming the nature of scientific computing. Some well-known examples in artificial intelligence (AI) and data science include: stochastic gradient descent methods for the training of deep neural networks; compressive sensing and random projections for data reduction; and randomized numerical linear algebra for massive and streaming data analysis.

In the context of this funding opportunity announcement (FOA), “randomized algorithms” are algorithms that use some form of randomness in their internal algorithmic decisions to achieve faster time to solution, better algorithmic scalability, enhanced reliability or robustness, or other improvements in scientific computing performance. Randomized algorithms have a long history. In the 1950s, the Markov Chain Monte Carlo method was central to the earliest computing efforts of the Atomic Energy Commission (the organization that preceded the Department of Energy). By the 1990s, randomized algorithms were used for such tasks as randomized routing in Internet protocols, the well-known Quicksort algorithm, and polynomial factoring for cryptography. In the early 2000s, compressive sensing – which is based on random matrices and sketching of signals – dramatically changed signal processing. Similarly, random forests and other ensemble classifiers have shown that randomization in machine learning can improve the tradeoff between bias and variance. In the past decade, novel randomization results have emerged from linear algebra and optimization research to address extreme-scale scientific computing challenges.

The research and development of randomized algorithms will provide an important foundation for advances in AI, data science, and scientific computing. Fundamental properties of randomness can be harnessed to address massive data and post-Moore computational grand challenges. Research topic areas of interest include approaches for dealing with:

• High computation and communication complexity and the development of efficient algorithms,
• High data dimensionality and finding sparse representations for data from scientific instruments and user facilities,
• Better algorithm scalability for low-power, high-performance edge computing,
• Reduced ill-conditioning and sensitivity for inverse problems, and
• Improved algorithm reliability and robustness to noise.

Extreme-scale science recognizes that disruptive technology changes are occurring across the science applications, algorithms, computer architectures and ecosystems. Recent reports and trends are heralding the convergence of high-performance computing, massive data, and scientific machine learning on increasingly heterogeneous architectures. Furthermore, the concept of programming is evolving thanks to neural networks that can learn from massive amounts of training data (without being explicitly programmed). Significant innovation will be required in the development of good paradigms and approaches for realizing the full potential of randomized algorithms for scientific computing. Proposed research should not focus strictly on a specific science application, but rather on creating the body of knowledge and understanding that will inform future advances in extreme-scale science. Consequently, the funding from this FOA is not intended to incrementally extend current research in the area of the proposed project. It is expected that the proposed projects will significantly benefit from the exploration of innovative ideas or from the development of unconventional approaches.