On solving linear systems in sublinear time
From MaRDI portal
Recommendations
- Approaching optimality for solving SDD linear systems
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Cites work
- A Note on the Inversion of Matrices by Random Walks
- A quantum-inspired classical algorithm for recommendation systems
- Algorithms, graph theory, and linear equations in Laplacian matrices
- An Efficient Method for Generating Discrete Random Variables with General Distributions
- Exact Kolmogorov and total variation distances between some familiar discrete distributions
- Expander graphs and their applications
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Exponential separation of quantum and classical communication complexity
- Finding sparse cuts locally using evolving sets
- Graph sparsification by effective resistances
- Local Computation of PageRank Contributions
- Lx = b
- Multiscale matrix sampling and sublinear-time PageRank computation
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- On approximating the stationary distribution of time-reversible Markov chains
- Powers of tensors and fast matrix multiplication
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum one-way communication can be exponentially stronger than classical communication
- Quantum recommendation systems
- Ramanujan graphs
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Solving local linear systems with boundary conditions using heat kernel pagerank
- Sparsified Cholesky and multigrid solvers for connection Laplacians
- Survey of local algorithms
- Using PageRank to Locally Partition a Graph
- Variable time amplitude amplification and quantum algorithms for linear algebra problems
- \texttt{PageRank} and random walks on graphs
Cited in
(10)- Upper bounds on the complexity of solving systems of linear equations
- Analysis of the binary complexity of asymptotically fast algorithms for linear system solving
- Sublinear P system solutions to NP-complete problems
- Sublinear Algorithms for Local Graph-Centrality Estimation
- Optimal fine-grained hardness of approximation of linear equations
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Randomly sparsified Richardson iteration: a dimension-independent sparse linear solver
- Solving Linear Programs in the Current Matrix Multiplication Time
- Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
- A queueing network-based distributed Laplacian solver
This page was built for publication: On solving linear systems in sublinear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090373)
