AI Bibliography |
Spielman, D. A., & Teng, S.-H. 2004, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Paper presented at Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. |
Resource type: Proceedings Article BibTeX citation key: Spielman2004 View all bibliographic details |
Categories: Artificial Intelligence, Complexity Science, Computer Science, Data Sciences, Decision Theory, General, Mathematics, Military Science Subcategories: Analytics, Chaos theory, Command and control, Edge AI, Fog computing, Forecasting, JADC2, Machine learning, Neural nets Creators: Spielman, Teng Publisher: Collection: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing |
Attachments |
Abstract |
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.
|