Abstract: Randomized algorithms have propelled advances in artificial intelligence and represent a foundational research area in advancing AI for Science. Future advancements in DOE Office of Science priority areas such as climate science, astrophysics, fusion, advanced materials, combustion, and quantum computing all require randomized algorithms for surmounting challenges of complexity, robustness, and scalability. This report summarizes the outcomes of the workshop, "Randomized Algorithms for Scientific Computing (RASC)," held virtually across four days in December 2020 and January 2021.
Introduction: The "Data Tsunami"
The scientific community is currently navigating a "colossal paradox." While our ability to generate data—through sensors like the ITER fusion reactor or high-fidelity exascale simulations—has exploded, our capacity to analyze this data using traditional means has reached a bottleneck. As data scales toward petabytes per day, deterministic algorithms, which require exact bit-for-bit consistency, are becoming computationally and energetically prohibitive.
The Exascale Paradox
In the era of exascale computing, the cost of a floating-point operation (FLOP) has become negligible. However, the cost of moving data—whether across a network or from memory to the processor—remains high in terms of both time and energy. Traditional deterministic methods often necessitate multiple passes over massive datasets, creating a significant data-movement bottleneck. Furthermore, emerging hardware paradigms, such as quantum and neuromorphic computing, are inherently non-deterministic. Rigid, classical algorithms are often a poor fit for these noisy environments.
Methodological Innovations
To address these challenges, the RASC workshop highlighted a shift toward algorithms that leverage internal randomness. Key techniques include:
- Sketching: This involves replacing a massive dataset with a significantly smaller "sketch" that retains essential mathematical properties, such as shape or volume. Remarkably, the size of these sketches can often be independent of the original data size.
- Randomized Linear Algebra: By using random projections, researchers can solve least-squares problems or perform low-rank factorizations in a single pass, drastically reducing the need for data movement.
- Data-Driven Sampling: Moving beyond simple uniform sampling, "scientifically informed" sampling identifies critical features or rare events within a simulation—the proverbial "needle in the haystack."
- Streaming Algorithms: These process data in real-time as it arrives from sensors, utilizing minimal memory. For instance, the Morris counter can count to $N$ using only $\log \log N$ bits.
Strategic Insights for AI for Science
The workshop identified several core principles for the future of scientific computing:
- Prioritize Data Movement over FLOPs: The primary utility of randomized algorithms today is minimizing data transit across machines.
- The "Sketch-to-Solve" Paradigm: A well-constructed random sketch can provide a solution that is "good enough" with high probability, often accompanied by a certificate of correctness.
- Hardware Alignment: Randomized algorithms are a natural fit for next-generation non-deterministic hardware. Rather than mitigating noise, these algorithms embrace it.
- Cultural Shift: A significant hurdle is the scientific expectation of "machine precision." New metrics are needed to balance speed, energy efficiency, and reliability, especially when underlying physical models already contain inherent uncertainties.
Key Results and Impact
The report highlights transformative potential across various domains:
- Complexity Reduction: Randomized trace estimation has shown the ability to reduce computational complexity from $O(n^3)$ to $O(n)$.
- Data Compression: In tsunami simulations, data-driven sampling captured salient features using only 2% of original grid points, where naive sampling failed entirely.
- Optimization: Methods like Stochastic Gradient Descent (SGD) are already foundational to AI; the report advocates for their formal integration into classical partial differential equation (PDE) solvers.
Challenges and Future Directions
Widespread adoption faces several roadblocks:
- Reproducibility: Randomized algorithms break the tradition of bit-wise identical results, necessitating new probabilistic debugging frameworks.
- The Curse of Dimensionality: High-dimensional DOE problems require better theoretical bounds for sketching methods.
- Expertise Gap: There is a critical need to bridge the gap between theoretical computer scientists and domain scientists in physics and chemistry.
- Software Infrastructure: Current libraries (BLAS/LAPACK) are deterministic. A new "Randomized Software Abstraction" layer is required for composability across DOE laboratories.
Summary updated