2025-07-23 –, Main Room 4
The DARPA-MIT SmartSolve project tackles the challenge of dynamically selecting optimal algorithms and architectures through an automated discovery framework. As part of this effort, we present advances on optimizing algorithm and data structure choices tailored to linear algebra. Contributions include automated benchmarking across diverse matrix patterns, database-driven selection via Pareto analysis, and exploring large language models for automatic heuristic generation.
Background. Matrix factorizations are fundamental in mathematics and computer science, enabling efficient solutions to various computational problems. In particular, LU decomposition—essentially the matrix form of Gaussian elimination—enables the efficient solution of linear systems and the computation of determinants (via forward/backward substitution and diagonal products). Moreover, specialized LU algorithms—such as banded LU and KLU—exploit the matrix pattern to reduce both computational and memory costs compared to general‐purpose methods.
Popular linear algebra libraries in Julia, Python, and MATLAB incorporate heuristics to automatically select optimal algorithms based on matrix characteristics, particularly for solving linear systems. Despite their success, the continuous development of new algorithms tailored to specific matrix patterns [1] requires improved selection strategies. Given the cost and impracticality of manual criteria determination, automated heuristic generation is crucial. To address these needs, the SmartSolve project, funded by DARPA-DIAL [2], is developing a toolbox that utilizes existing matrix pattern databases [3] to systematically benchmark the performance and accuracy of diverse algorithms across various computational architectures. This approach leverages aforementioned benchmark data and automated classification techniques to generate heuristics that adaptively select optimal solutions for diverse inputs.
Large language models (LLMs), with their extensive trainable parameters, offer a powerful approach for identifying trends and patterns in data. Initiatives such as ChatHPC have demonstrated their potential by generating optimized code, leading to substantial computational speedups [4, 5]. As these models continue to advance at an exponential rate, they hold significant promise for the SmartSolve project for automatic heuristics generation.
Contribution. We present our work on a key component of SmartSolve.jl—the automated discovery of optimal algorithms and data structures. Furthermore, we analyze opportunities and limitations of LLMs in algorithmic selection and in heuristic generation.
The discovery process follows a structured approach. First, a diverse set of matrix patterns and data structures—such as dense, sparse, and banded—is provided as input. For each pattern and data type, performance metrics, including casting time, computation time, and accuracy, are systematically measured to construct a comprehensive database. Algorithms are selected based on timing and accuracy, resulting in an optimized smart database. To achieve this, an automated Pareto analysis is performed to identify the most efficient and accurate algorithms while illustrating performance variations across different patterns [6]. For certain matrix patterns, selecting the optimal combination of algorithms and data structures can achieve over a 50X speedup, surpassing the default selections in major linear algebra libraries.
To further enhance algorithm selection, we explore the integration of LLMs within SmartSolve.jl. Preliminary experiments with Llama 3 demonstrate its ability to classify and recommend optimal algorithms and data structures. In the course of the present investigation we will scale these experiments to large matrices and benchmark Llama 3 against the package’s existing tree-based machine learning models. Our evaluation will determine whether LLM-driven classification can deliver greater speedups and accelerate heuristic generation for dynamic algorithm selection.
Research Impact. This project could mark an important step forward in integrating artificial intelligence models with heuristic-driven strategies to optimize computational linear algebra performance. It is among the first to leverage LLM technology for intelligent algorithm selection in LU and QR decompositions, moving beyond traditional static approaches. SmartSolve.jl aims to deliver automated heuristics that can be seamlessly integrated into widely used computational libraries. Furthermore, if the LLM-based approach proves effective, it could substantially accelerate heuristic generation, facilitating the rapid adoption of cutting-edge algorithms in scientific software.
Relevance to the Julia Community. The Julia linear‐algebra ecosystem—anchored by widely adopted packages like LinearSolve.jl and the standard LinearAlgebra.jl—offers a rich suite of factorization methods to a broad community of users. Enhancements in SmartSolve.jl could further optimize these packages, delivering significant performance benefits to thousands of users.
References.
[1] Li (2005). DOI: 10.1145/1089014.1089017.
[2] MIT's SmartSolve, DARPA-DIAL. https://github.com/JuliaLabs/SmartSolve.
[3] Zhang and Higham (2016). DOI: 10.7717/peerj-cs.58.
[4] Latif and Zhai (2024). DOI: 10.1016/j.caeai.2024.100210.
[5] Yin et al. (2024). DOI: 10.1007/s11.
[6] Hoefler and Belli (2015). DOI: 10.1145/2807591.2807644.
Computer Scientist. MIT's Julia Lab.
I am a postdoctoral researcher at the MIT JuliaLab and an HPC enthusiast who loves solving complex problems by thinking in parallel. My research intersects High-Performance Computing (HPC) and Artificial Intelligence (AI), exploring how advanced computational techniques can optimize AI algorithms for increased efficiency and effectiveness. I was honored as one of the Rising Stars in Computational and Data Sciences by U.S. Department of Energy. My collaborations extend internationally, including with the Innovative Computing Lab at the University of Tennessee and MINES ParisTech. In Summer 2021, I was a visiting scholar at the Innovative Computing Lab, where I contributed to a milestone of the Software for Linear Algebra Targeting Exascale (SLATE) project , a joint initiative of the U.S. Department of Energy’s Office of Science and the National Nuclear Security Administration (NNSA).
Student at MIT majoring in Physics and CS. Researching efficient algorithmic selection as part of the SmartSolve group.