Hardness Results for Structured Linear Systems

DOI10.1137/17M1161774zbMath1462.65049arXiv1705.02944OpenAlexW3008021696MaRDI QIDQ5117379

No author found.

Publication date: 25 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.02944

zbMATH Keywords

numerical linear algebracomplexity theorylinear system solversmulticommodity flow problemsfine-grained complexityLaplacian solverstotal variation matricestruss stiffness matrices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Numerical linear algebra (65F99)

Related Items (max. 100)

Hardness of graph-structured algebraic and symbolic problems ⋮ Space Hardness of Solving Structured Linear Systems.

Uses Software

• RecPF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating projection, ptychographic imaging and phase synchronization
• Fast approximation algorithms for multicommodity flow problems
• On factor width and symmetric \(H\)-matrices
• Gaussian elimination is not optimal
• Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• Phase Retrieval with Polarization
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Computational Advertising: Techniques for Targeting Relevant Ads
• Runtime guarantees for regression problems
• Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming
• A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
• Stable Camera Motion Estimation Using Convex Programming
• The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
• Rigidity in Finite-Element Matrices: Sufficient Conditions for the Rigidity of Structures and Substructures
• Two-Commodity Flow
• Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)
• Stability of the Lanczos Method for Matrix Function Approximation
• Viewing Direction Estimation in Cryo-EM Using Synchronization
• Incomplete nested dissection
• Solving SDD linear systems in nearly m log ^1/2 n time
• Geometric median in nearly linear time
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Faster approximate multicommodity flow using quadratically coupled flows
• Multiplying matrices faster than coppersmith-winograd
• Second-order Cone Programming Methods for Total Variation-Based Image Restoration
• Image Processing and Analysis
• Methods of conjugate gradients for solving linear systems

This page was built for publication: Hardness Results for Structured Linear Systems