Inaugural Midwest Randomized Linear Algebra Workshop

Title: (Randomized) numerical linear algebra

Abstract: Numerical Linear Algebra (NLA) has long been a cornerstone of scientific computing, powering advancements in physics, engineering, and beyond. This talk explores how Randomization in NLA (RandNLA) has emerged as a transformative force in data science, machine learning, and artificial intelligence by leveraging randomness to accelerate computations and reduce dimensionality. We will conclude by discussing a modern application of RandNLA to stochastic rounding and its regularization properties.

Title: Possible futures for randomized numerical linear algebra

Abstract: Randomized Numerical Linear Algebra (RandNLA) is at an inflection point, and the community needs to decide how it wants to proceed. Classical RandNLA was based on subspace embeddings and Johnson-Lindenstrauss methods. It led to remarkable theoretical improvements; and, when used as preconditioners for traditional NLA algorithms, it led to high-quality numerical implementations that clearly improved upon traditional deterministic NLA methods, for a range of problems. In many cases, however, these threads proceeded in parallel. In recent years, however, we have witnessed novel theoretical developments based on novel embeddings with closer connections to non-asymptotic random matrix theory, novel use cases and user requirements coming from machine learning (ML) and artificial intelligence (AI), and novel demands in the every-changing hardware landscape, including low precision and multiple (medium, low, and very-low) precision computation. Recent developments in RandNLA make it uniquely poised to address these interdisciplinary challenges. In this talk, I'll review some history, some projects on trying to use RandNLA to build the foundations for linear algebra in the modern AI/ML era, and recent research results that hold the potential to tie these directions together.

Title: The sensitivity of the normal equations for least squares problems with randomized preconditioners

Abstract: We start by presenting examples for the sensitivity of least squares problems, and reviewing the role of perturbation theory. Then we consider least squares problems for real matrices of full column-rank, and analyze the sensitivity of the solution from several types of normal equations, which are preconditioned by a randomized preconditioner computed in lower precision. Our perturbation bounds are realistic and informative, and suggest that the conditioning depends only mildly on the quality of the preconditioner; however, it does depend on the size of the least squares residual -- even if the normal equations do not originate from a least squares problem. We illustrate that a randomized preconditioner can deliver a solution accuracy comparable to that of Matlab's mldivide command, is efficient in practice, and well-suited to GPU implementations.

Tutorial: Foundations of randomized numerical linear algebra

Details: Randomized Numerical Linear Algebra (RandNLA) describes a suite of algorithms which use randomness to construct small representations (sketches) of large data matrices. These sketches are then used to efficiently solve large-scale matrix problems at the core of many scientific, data science and machine learning tasks. This tutorial will overview the algorithmic and theoretical foundations of RandNLA, including such topics as randomized dimensionality reduction, matrix sketching and sampling, least squares, and low-rank approximation, with a particular focus on recent applications to machine learning and optimization.

Tutorial: Using randomized linear algebra on example applications in Julia

Step 1: Please install Docker and pull npritch92895/randlinearalgebra_examples.

Step 2 (Option 1): From the desktop application, you can run the container by clicking run from the Images tab. Under the optional settings, please type in 8888 into the host port.

Step 2 (Option 2): If you are using the command line interface, please use docker run --rm -p 8888:8888 randlinearalgebra_examples.

Step 3: You can now access the container by visiting localhost:8888 in your browser.

If all else fails, clone the repo directly: https://github.com/nathanielpritchard/RandLinearAlgebra_examples.

Tutorial: Easy* Python wrappers for RandBLAS and RandLAPACK

Step 1: Please install Docker and conda.

Step 2: Please clone this repository to your machine.

Step 3: From your command line interface use docker pull ghcr.io/rileyjmurray/randlapack-python-workshop:latest to pull the image.

Discord Channel: if you are interested, join the RandLAPACK Discord Channel.

Multiple community members have independently identified this gap: turning algorithms into reusable, production-quality software that non-experts can use remains an unsolved problem. This session addresses the design principles for a community software ecosystem — architecture decisions (low-level kernels vs. high-level problem-solving environments), automatic parameter tuning to remove the need for expert configuration, interoperability with existing numerical libraries, and long-term governance and maintenance models. This maps directly to OAC's Cyberinfrastructure for Sustained Scientific Innovation (CSSI) program and its investments in sustainable scientific software.

Facilitator: Jiaming Yang

Participants

• Piotr Luszczek
• Max Melnichenko
• Nathaniel Pritchard
• Chao Chen
• Riley Murray
• Ilse Ipsen
• Raphael Meyer
• Joshua Cape

On modern architectures, communication and data movement (not floating-point operations) are the dominant cost. Randomized methods have natural communication-avoiding properties that make them uniquely suited to current and emerging hardware, but only if algorithms are designed with hardware realities in mind rather than ported after the fact. This session examines algorithm-hardware co-design: reduced-precision arithmetic, GPU-native algorithm formulations, memory hierarchy awareness, and what RandNLA specifically enables on exascale and post-exascale systems. The findings feed into OAC's infrastructure investments, including ACCESS allocations and leadership computing facility planning.

Facilitator: Sachin Garg

Participants

• Longfei Gao
• Vishwas Rao
• Daniel Bielich
• Rob Webber
• D. Adrian Maldonado
• Qin Li
• Chris Geoga
• Vivak Patel
• Shambhavi Suryanarayanan

Foundation models, scientific machine learning, and AI for science are consuming enormous resources and NSF attention. Randomized linear algebra sits beneath many of these workloads (sketching for dimensionality reduction, randomized preconditioning for optimization, sampling for efficient training) yet RandNLA is not yet a first-class citizen in mainstream ML frameworks. This session asks what it would take to embed RandNLA into the national AI cyberinfrastructure: integration with PyTorch/JAX/Flux, support for foundation model training pipelines, active learning for data-efficient science, and gradient estimation for derivative-free and multi-fidelity settings. This connects to OAC's growing AI infrastructure portfolio.

Facilitator: Kate Pearce

Participants

• Kevin Miller
• Stephen Becker
• Garvesh Raskutti
• Keith Levin
• Yifu Wang
• Michael Mahoney
• Michal Derezinski
• Petros Drineas

Scientists and engineers need guarantees, not just probabilistic statements. A structural engineer or climate modeler needs to know what "information is preserved with probability at least 1 − p" means for their specific workflow. This session tackles the gap between the theoretical guarantees that RandNLA provides and the deterministic-feeling reliability that practitioners expect. Topics include fixed-precision algorithms that automatically determine sufficient rank, perturbation theory under sketching, connections to random matrix theory for sharper analysis, and verification/validation frameworks. Closing this trust gap is essential for adoption of randomized methods across NSF-funded scientific computing facilities.

Facilitator: Raphael Meyer

Participants

• Chao Chen
• Garvesh Raskutti
• Joshua Cape
• Stephen Becker
• Michal Derezinski
• Max Melnichenko
• Riley Murray
• Longfei Gao
• Jiaming Yang

RandNLA sits at an intersection of pure mathematics, computer science, high-performance computing, and domain science that few graduate programs adequately cover. As the field matures and its methods become infrastructure, the question of who builds, maintains, and uses that infrastructure becomes urgent. This session brings together senior leaders who have built training programs with early-career researchers who can speak to gaps in their own preparation. The goal is concrete recommendations for OAC: training grants, curriculum development, research experiences for undergraduates, cross-disciplinary postdoc programs, and short-course or summer school models that have proven effective.

Facilitator: Nathaniel Pritchard

Participants

• Petros Drineas
• Ilse Ipsen
• Michael Mahoney
• Keith Levin
• Piotr Luszczek
• Sachin Garg
• Vivak Patel

Rather than starting from algorithms and asking where they apply, this session works backwards: starting from scientific and engineering bottlenecks and asking what RandNLA can unlock. Participants bring case studies from large-scale simulation, Gaussian processes, PDE-based inverse problems, industrial eigensolvers, and active learning for computational engineering. The goal is to identify specific scientific problems that are currently intractable or prohibitively expensive where randomized methods could provide a transformative advantage, and to articulate the infrastructure investments needed to realize that advantage. This grounds the report in the concrete scientific impact that OAC exists to enable.

Facilitator: Yifu Wang

Participants

• Vishwas Rao
• Chris Geoga
• Qin Li
• Daniel Bielich
• Kevin Miller
• Rob Webber
• Shambhavi Suryanarayanan
• Kate Pearce
• D. Adrian Maldonado