Papers › Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth
Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth
Richard Y. Zhang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
If a sparse semidefinite program (SDP), specified over n×n matrices and subject to m linear constraints, has an aggregate sparsity graph G with small treewidth, then chordal conversion will sometimes allow an interior-point method to solve the SDP in just O(m+n) time per-iteration, which is a significant speedup over the Ω(n³) time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by an O(1) treewidth in G that is independent of m and n, as a diagonal SDP would have treewidth zero but can still necessitate up to Ω(n³) time per-iteration. Instead, we construct an extended aggregate sparsity graph G̅⊇G by forcing each constraint matrix Aᵢ to be its own clique in G. We prove that a small treewidth in G̅ does indeed guarantee that chordal conversion will solve the SDP in O(m+n) time per-iteration, to ϵ-accuracy in at most O(√(m+n)log(1/ϵ)) iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-k-CUT relaxation, the Lov\'asz theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections