44 ms·
New algorithm breaks speed limit for solving linear equations
- cperciva 6y agoStripping out the fluff: The authors proved that iterative methods for solving sparse linear systems can be guaranteed to be faster than the best methods of solving dense linear systems.
- deleted 6y ago[deleted]
- waheoo 6y agoWhy is this noteworthy? (I assume this is common knowledge or at least should be)
- alisonkisk 6y agoIt wasn't known to anyone before.
- stanmancan 6y agoNot sure why you’re being downvoted here; I’d like to know why this is noteworthy as well!
- sgillen 6y agoIt's being downvoted because it comes across as someone arrogantly dismissing an important work because they have no idea what they are talking about. If they instead asked "why is this noteworthy? in my ignorance this seems obvious", they might have gotten a better reception.
- ButtSpark69 6y agoInteresting, I just took it at face value. I wonder what the % split is.
- sdenton4 6y agoWith a sparse system, you might run into dependency chains that effectively make it dense. Like in an adjacency matrix for a graph, you may have a lot of sparsity, but if you're forced to consider neighbors of neighbors, the adjacency matrix you need is A^2. This can be dense even if A is quite sparse.
- motoboi 6y agodeep learning uses a lot lot of sparse linear systems
- jtsiskin 6y agoFor some easy to grok examples: imagine MNIST, where all the pixels besides the writing are 0; or a recommendation system, where column i has the users rating for movie i, or number of times they listened to song i; or any one-got encoding scheme
- eru 6y ago> or any one-got encoding scheme Typo: should be one-hot encoding scheme. Sparsity of input isn't often relatively easy to achieve, as you suggest. Sparsity of intermediate layers requires more work. (But is often a good regularization technique.)
- jtsiskin 6y agoHumorously “one-got” is almost a apt description :)
- johncolanduoni 6y agoIt does, but the problem this algorithm handles is dealing with demanding convergence for all input matrices without adding an additional “n” factor to handle increased precision. Meanwhile deep learning is moving in the direction of 16-bit floating point and 8-bit integer scalars.
- vector_spaces 6y agoMarrix multiplication is fundamental to basically any numerical method you can think of, with applications ranging from machine learning to numerical solutions to differential equations to graph algorithms used in network analysis
- johncolanduoni 6y agoThis method converges unconditionally for any input with the required sparsity when using numerical representations with a fixed number of bits. No traditional sparse iterative solver has that property without further conditioning the matrix or increasing the run-time to handle the higher precision. As they lay out in the paper (third paragraph of introduction section on the preprint), for certain (rare in practice) matrices direct solvers still offered better runtime if convergence is demanded for all inputs with a certain sparsity. This article (not the paper) definitely oversells the immediate practical applications; nobody is going to throw out their CG solver and pick this method up in practice to guarantee convergence in this manner.
- lambda_obrien 6y agoIn practice, are there maybe a few problems for which this guarantee unlocks a big performance speedup? How might this be used practically?
- deleted 6y ago[deleted]
- Moodles 6y agoI don't think the article was bad enough to call it "fluff". Also the result is technically "guaranteed to be faster than the *currently best known* methods of solving dense linear systems", no? It might be the case that there's still some better way involving matrices that's faster than this iterative guessing method. Or did they prove that none could possibly exist?
- oscardssmith 6y agoThey proved that any dense algorithm of n^w where w>2 can be made more efficient. Note that 2 is a trivial lower bound for w.
- pfortuny 6y agoThanks, this is much more interesting.
- singhrac 6y agoOne of the co-authors, Richard Peng, is well known in the competitive programming community (he has helped train the US IOI team in years past).
- angry-tempest 6y agoSantosh Vempala is also considered to be a genius, at least in the statistical learning community. I don't know how he didn't get tenure from MIT though
- rosstex 6y agoAccording to his CV, he did get tenure.
- Cyph0n 6y agoAt Georgia Tech, not at MIT. Still a great achievement though (go Jackets!). Edit: my bad, looks like he was an associate prof at MIT, which means he was indeed tenured before moving to Tech!
- aoki 6y agoI have no idea what happened in this case, but that doesn't follow - MIT is one of those schools that routinely promote to associate without necessarily giving tenure [0]. [0] https://thetech.com/2010/06/11/tenure-v130-n28 https://thetech.com/2010/06/11/tenure-v130-n28
- rosstex 6y agoInteresting, thanks!
- tracyhenry 6y agoThere is a position at MIT called associate prof without tenure. So just because he was an associate prof doesn't necessarily mean he had tenure.
- deleted 6y ago[deleted]
- stakkur 6y agoIf you only know there are 10 heads and 30 feet, how many chickens are there, and how many pigs? As algebra students learn, there’s a set procedure for figuring it out If there are 30 feet, then there are 15 chickens. Because pigs don't have feet. Where do I pick up my algebra prize?
- deleted 6y ago[deleted]
- Google234 6y agoIt’s sad that 5 of those chickens don’t have heads
- meepmorp 6y agoIt’s less of a limitation than you’d think: https://en.wikipedia.org/wiki/Mike_the_Headless_Chicken https://en.wikipedia.org/wiki/Mike_the_Headless_Chicken
- deleted 6y ago[deleted]
- 8bitsrule 6y agoGo with the 3-legged chickens instead.
- e79 6y agoThe “smart guessing” approach reminds me a lot of SAT solving. Certain search problems become easier when you introduce randomness and clever heuristics to optimize and guide your guesses. Edit: And here’s a link to the paper discussed in the article for anyone who is curious: https://arxiv.org/abs/2007.10254 https://arxiv.org/abs/2007.10254
- mabbo 6y ago> “Philosophically we didn’t know before if you can go faster than matrix multiplication,” said Vempala. > Now we do. This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines. Now all that's left is the matter of making this practical.
- eru 6y agoYou might like Scott Aaronson's 'Why Philosophers Should Care About Computational Complexity' https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf
- JonathanMerklin 6y agoIf this paper whets your appetite (talking mostly to grandparent comment, but also HN at large) OR alternatively if you think that this paper is a bit too advanced for your knowledge level, I implore you to read Scott Aaronson's book "Quantum Computing Since Democritus". The book is one of the finest in the genre of "too casual to be a textbook, too informative to be an easy read for laymen" nonfiction, and it is primarily concerned with philosophy vis-à-vis computational complexity. It does a pretty good job at assuming you only have a bit of computer science background (pun unintended, noticed, left in) and builds your knowledge base up from introductory set theory and first order logic in the earliest pages (In fact, it's based on a course he taught, and his lecture notes are available online and frequently make for fantastic supplemental material [1]). One of my favorite reads of 2020. [1] https://www.scottaaronson.com/democritus/ https://www.scottaaronson.com/democritus/
- c-smile 6y agoLooks like a description of simplex (and/or montecarlo) method for solving linear equations. Or did I get it wrong?
- alanbernstein 6y agoI believe the simplex method is for solving optimization problems, not linear systems?
- vitus 6y ago1. Simplex is used to solve linear programs, which are inequalities (not equations). While it's true that your solution will typically be on one of the vertices of your polytope, that just means that some (not necessarily all) of your constraints are hard constraints. 2. The worst-case time complexity of Simplex is exponential.
- c-smile 6y agoAFAIR first step of simplex method is to convert system of inequalities to system of equalities by adding weak variables and making tableau (matrix) of those. And then incrementally solve that. And usually simplex is considered as having polynomial complexity - close to their estimations.
- eru 6y agoSimplex uses solving systems of linear equations as a building block. Most variants of simplex have exponential runtime on worst case input. (But they do well in practice.) Recently, some variants of simplex with polynomial runtime have been found. Solving linear equations was always known to 'only' take polynomial amounts of time at most. But the question is whether that's n^3 or n^2 or something better..
- vitus 6y ago(I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables. Or even O(n^3). Because that's what's claimed here.) That's mostly correct. You end up with a system of equalities for _a subset_ of your points, which yields a single vertex. Ultimately with a linear program, you're trying to optimize an objective function, max w'x s.t. Ax <= b, x >= 0 (in canonical form). The x >= 0 constraint makes this nontrivial to translate from a linear equation Ax = b. If you magically knew the sign of each component of the solution, you'd be able to perform a simple variable substitution, but you generally don't, at least not without solving the system of equations. (And yes, you need that constraint, or else your LP is unbounded, and your solution ends up with a negative infinity in it.)
- jimbokun 6y agoThis was a very clear exposition and easy to follow, not knowing much about the topic. A very nice piece of writing.
- a_ghoul 6y agoI may be misunderstanding but they quote >“It only works when your matrix is sparse enough,” said Williams. This is still important but only for this subset of problems really.
- the_svd_doctor 6y agoIt’s a big subset though. Lots of linear systems come from PDE discretization and are structurally sparse with a fixed number of non zeros per row.
- a_ghoul 6y agoThat's very true. I especially would trust someone with your username!
- cambalache 6y agoYes, also the matrices that come out from Gaussian Processes
- Jweb_Guru 6y agoIn practice, the majority of the really big matrices I encounter are very sparse, because they're often constructed as a reduction from some other much smaller representation so we can use linear algebra methods.
- jl2718 6y agoWhat is the actual sparsity criterion to achieve this big-O bound? (Edit: found in arxiv - o(nω−1/log(κ(A))) non-zeros). Note also dependence on condition number.
- cevi 6y agoOne of my favorite little-known algorithmic facts is that a sparse system of n linear equations in n unknowns over a finite field can be solved in time O(mn) if the corresponding matrix has m nonzero entries[1]. I'm surprised at how hard it is to extend this to the reals - it seems like dealing with the precision issues is much tougher than I imagined. [1] http://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Wiedemann86.pdf http://www.enseignement.polytechnique.fr/profs/informatique/...
- jl2718 6y agoQuick scan: it seems that this result is a real extension of that result.
- champagnepapi 6y agois this gonna be on leetcode so we can prep? (jokes)
- endisneigh 6y agoGive it a few decades
- burlesona 6y agoNice work out of Georgia Tech. Go jackets!
- deleted 6y ago[deleted]
- k2xl 6y agoQuestion from someone who is not super knowledgable about this subject - is this conceptually similar to using ML to solve linear equations? I.e. randomly guess and update weights... Is there a field of research in using ML approaches for this type of problem?
- jl2718 6y agoAx=b could certainly be solved with gradient descent methods popular in ML, but this is a lot more direct than that. It’s a little more like solving random pieces until it all comes together.
- vendiddy 6y agoIf the same class of problems need to get solved on a regular basis, could the guessing algorithm get smarter with each iteration using ML techniques? Seems like if the algorithm is applied to a particular domain, there could be efficiencies gained from optimizing what guesses to rule out. Not very knowledgeable about the subject though.
- deleted 6y ago[deleted]
- Moodles 6y agoThat's really excellent writing. It explains the gist of it really well. I suspect the proof details are very complex though. It's also not clear if this method will practically be a speed up, or just asymptotically. It's still a very cool result though: I love how my intuition would tell me that solving matrix multiplication is surely the fastest way, and then someone comes along and explains this method and my brain goes "oh yeah, that does make sense it could be faster". That's the beauty of certain results and explanations.
- toolslive 6y agoMy feeling was just the opposite. I was constantly thinking "stop acting like I'm 12 and have 0 knowledge about linear algebra." As usual, it just depends what your context is, and the author will be happy to know there's an audience that finds it excellent.
- Moodles 6y agoI have a master's degree in math and a PhD in STEM so I know how linear algebra works. So when I say it's excellent writing, I don't mean perfectly calibrated for me or you. I mean it's excellent writing for a wide audience to get the gist of it. I think that's very difficult to do for math. An average 12 year old would not understand matrices without a very clear explanation. Having taught math to both children and undergrads, I think it's very easy to underestimate how easy it is once you already understand it. A sentence like: > for any ε > 0 and 0 < δ < 1, using poly(dimension, #nonzeros, condition, 1/ε, 1/δ) floating-point operations, our algorithm finds a solution having less than ε error with probability 1 - δ. Would confuse the shit out of most people. This video explains really beautifully what I mean: https://www.youtube.com/watch?v=M64HUIJFTZM https://www.youtube.com/watch?v=M64HUIJFTZM
- vendiddy 6y agoIt seems like there's a lot of potential for domain specific optimization if we can improve the guessing algorithms.
- blt 6y agoI felt the article undersold an important technical detail about this work. Many randomized algorithms have a "with high probability" guarantee, which for linear systems might look like: for any ε > 0 and 0 < δ < 1, using poly(dimension, #nonzeros, condition, 1/ε, 1/δ) floating-point operations, our algorithm finds a solution having less than ε error with probability 1 - δ. However, that is not the kind of guarantee stated in Theorem 1.1 in the paper. Even though the algorithm uses randomness, the analysis yields a classic big-O complexity guarantee that does not involve probabilities. This is a big difference, and it makes the result stronger.
- eru 6y agoSee also https://en.wikipedia.org/wiki/Las_Vegas_algorithm https://en.wikipedia.org/wiki/Las_Vegas_algorithm and compare with https://en.wikipedia.org/wiki/Monte_Carlo_algorithm https://en.wikipedia.org/wiki/Monte_Carlo_algorithm
- leapis 6y agoIs this a theoretical difference, or a difference in terms of an actual implementation? I have no knowledge of linear systems algorithms, but as far as I was aware, many w.h.p algorithms resolve to correctness with probability of 1 - (1/n)^c (with c effectively being a hyperparameter), which would seem like quite a strong result in itself.
- YetAnotherNick 6y agoI think that is definition of approximate algorithm, not randomized algorithm. Quicksort is a classic randomized algorithm, but it is not approximate.
- bonzini 6y agoRandomized quick sort could pick the wrong pivot at every step (or at every other step, that's still quadratic complexity), so it's only O(n log n) with high probability.
- zeroonetwothree 6y ago
- jl2718 6y ago“In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any ω>2. This speedup holds for any input matrix A with o(nω−1/log(κ(A))) non-zeros, where κ(A) is the condition number of A. For poly(n)-conditioned matrices with Õ(n) nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1/poly(n) error is O(n2.331645). Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC `06 `07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.”
- heisenbit 6y agoHmm, somehow reminds me of my controls classes way back where I learned that injecting some random noise in the measurements of a closed loop can actually help the estimator to converge better.
- vendiddy 6y agoInteresting, is there a laymen explanation of why this might help?
- bodhiandpysics1 6y agoits really simple... in rough terms it breaks loops that your estimator might get itself in! Imagine you estimator is a dynamic system, and while its converging it get trapped in a cycle between two values. Adding a little noise can break this cycle.
- zzleeper 6y agoDoes anyone know how big are the constant terms here? A few years ago I studied and partly implemented an earlier (related?) work by Peng (on graph laplacians and SDD systems: https://epubs.siam.org/doi/abs/10.1137/110845914 https://epubs.siam.org/doi/abs/10.1137/110845914 ) and the big-O improvements did not seem to compensate for the larger constant.
- jmblpati 6y agoThe constants are galactic: any 'fast matrix multiplication' algorithm outside of Strassen's algorithm has some incredible constants that are somewhat intrinsic to the recursive framework. The algorithm is primarily of theoretical importance (prior to this no one knew whether sparsity significantly helped methods of this type for solving linear systems), but it is not implementable. However the block Krylov algorithm itself presented in this paper has a little bit more of a chance of being implementable than fast matrix multiplication (the matrix multipliciation is only used to solve small linear systems to deal with small eigendirections in the Krylov subspace). I am still skeptical that this is a truly practical algorithm due to its complexity, but unlike the case of generic FMM there is no obvious bottleneck. On the other hand, in recent years Dan Spielman and collaborators have been working on fast implementations of Laplacian solvers: https://github.com/danspielman/Laplacians.jl https://github.com/danspielman/Laplacians.jl I believe a lot of the fixed constants and combinatorial routines are changed from what is theoretically provable, but from screwing around with the code in the past it seems very fast in practice.
- graderjs 6y agoFACTORING is going to be next, right?
- midjji 6y agoThere are no matrix multiplications in linear solvers in general. There are Matrix vector multiplications, typically far fewer than the size of the matrix. This confusion hides that solving linear systems was already far faster than matrixmatrix multiplication, and makes it seem like a stronger result than it is. I would like to see this compared to e.g. sparse cg, for any non random datamatrix.
- thomasahle 6y agoThis is a theoretical result - for now at least. Theoretically the fastest linear solvers run in time n^w where w ~ 2.3 is the matrix multiplication constant. In practice the fast matrix multiplication algorithms are not that fast, so they aren't used for linear solvers.
- azinman2 6y agoWhat is the memory usage like on this compared to existing dense solvers?
- mik09 6y agoi don't totally underestand this, but looks similar to quadratic sieve. still this is amazing.
- mh-cx 6y agoFor those that need a concise refresher on - or introduction to - linear equations there's an (as usual) excellent series of 15 short videos from 3blue1brown: https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFit...
- adenozine 6y agoIsn't going faster a probabilistic property then? If it's random numbers, how could it be always faster? What about a genetic algorithm? That's the same principle of guess and check.
- alpineidyll3 6y agoWake me up when it's in LAPACK. Then replace DGBSV, and don't tell me.
- lamontcg 6y agoThis reads a little bit like simulated annealing or basin hopping algorithms at the random initial guess part.