Skip to main content
Artificial Intelligence

Large-scale semidefinite programming with graphics processing units.

| Source: Proceedings of the National Academy of Sciences of the United States of America

Semidefinite programming (SDP) provides a powerful framework in applied mathematics with applications spanning optimization, machine learning, quantum computing, and beyond. However, the computational cost of solving large-scale SDP problems remains a significant practical limitation. We break this long-standing computational bottleneck through a synergistic codesign of low-rank algorithms and graphics processing unit (GPU) architectures, developing accelerated first-order methods that leverage

Semidefinite programming (SDP) provides a powerful framework in applied mathematics with applications spanning optimization, machine learning, quantum computing, and beyond. However, the computational cost of solving large-scale SDP problems remains a significant practical limitation. We break this long-standing computational bottleneck through a synergistic codesign of low-rank algorithms and graphics processing unit (GPU) architectures, developing accelerated first-order methods that leverage both algorithmic innovations and hardware-aware implementation to achieve up to 4 orders of magnitude improvements in speed and scalability for large-scale SDPs with sparse and low-rank structure, thereby opening frontiers in large-scale scientific computing. Our solver, GPU-accelerated Low-Rank Alternating Direction Method of Multipliers Splitting (cuLoRADS), exemplifies this approach, combining the Burer-Monteiro method with a splitting scheme to efficiently solve massive-scale SDPs. Specifically, it can solve a set of MaxCut problems whose matrix variables have dimensions of [Formula: see text] in 10 s to 1 min each on an NVIDIA H100 GPU with 80 GB of memory, whereas previously reported central processing unit solvers required dozens of hours. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a [Formula: see text] matrix variable and 2) a Minimum-Rank Matrix Completion problem with a [Formula: see text] million [Formula: see text] 20 million matrix variable and approximately [Formula: see text] million constraints, both in a matter of minutes. It also resolves a long-standing SDP computational barrier in the quantum ordered search problem, which had remained unsolved for 18 y.

Read the original source →

Related Stories

Artificial Intelligence

Simply aging.

Biological aging is complex and resists any single mechanistic narrative. This article develops a conceptual framework for aging biology through a series of brief statements on central topics in the field, with the goal of discussing aging simply, directly and accessibly. The organizing principle is that aging is a default outcome of living: because biological processes are inherently imperfect, deleterious changes (the deleteriome) accumulate over time and progressively erode functional reserve

Continue reading
Artificial Intelligence

An integrative single-cell epigenomic atlas annotates the regulatory genome of the adult mouse brain.

Histone modifications underpin the cell-type-specific gene regulatory programs that drive the remarkable cellular diversity of the mammalian brain. Here, we jointly profiled four histone modifications and the transcriptome in 2.5 million nuclei from the adult mouse brain. By integrating these data with chromatin accessibility, DNA methylation, and three-dimensional genome organization, we constructed a unified epigenomic atlas spanning over 100 brain cell subclasses and assigned active, primed,

Continue reading
Artificial Intelligence

Sub-second dopamine reinforcement shapes juvenile social play.

Juvenile social play is critical for neurodevelopment, yet the neural mechanisms organizing moment-to-moment interactions remain elusive. Using social behavior sequencing (Social-seq)-an occlusion-robust 3D pose estimation and unsupervised clustering pipeline-we found that nucleus accumbens (NAc) dopamine was tightly coupled to sub-second social syllables during naturalistic interactions. In wild-type juveniles, males exhibited a sharper dopaminergic contrast between proactive play and forced su

Continue reading
Artificial Intelligence

Where intention goes, responsibility flows: Grounding AI accountability in the machine learning paradigm.

An opening salvo of lawsuits in US courts has begun holding AI companies accountable through independent doctrinal routes: Product liability and agency law cut as swords, while the shields of Section 230 immunity and First Amendment doctrine begin to crack. This Perspective points out that these converging paths share a unifying principle, built on the very engineering architecture of machine learning (ML) itself. Every ML system, across all variants, is constituted by a human-specified objectiv

Continue reading
Artificial Intelligence

Intermittent gas-liquid rearrangement controls the mixing of gases in porous media.

Gas mixing in porous media governs important environmental and industrial applications in which multiple gas components share the available pore space with liquid water, simultaneously undergoing gas mixing and gas-liquid redistribution. Currently, this process is represented by macroscopic models that ignore pore scale dynamics. We demonstrate that this is not generally valid, and can lead to large errors in the mixing rate. We use 4D X-ray imaging to investigate nitrogen injection into a porou

Continue reading