4 ms·
A New Way To Solve Linear Equations (over finite fields)
- andrewcooke 14y ago...over finite fields (http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/Finite_field_arithmetic) which is cool for many things, but it's probably not what you expected from the title. tl;dr: filter a collection of random guesses one equation at a time. new trick is expanding the set of guesses as you work through, so you don't need to start with 2^n (if modulo 2) for example.
- ColinWright 14y agoI've edited the title - thanks.
- jps359 14y agoAs I understand it, the conjugate gradient method works over the reals.
- stephencanon 14y agoConjugate Gradient works over the reals if the matrix is symmetric positive definite.
- jmount 14y agoWhich can be arranged. Instead of solving for x in A x = b solve for x in t(A) A x = t(A) b (t() being transpose, and you may not need to explicitly form t(A) A).
- stephencanon 14y ago... which works, but the condition number of AtA is the square of the condition number of A, so convergence may be very slow, or the results may be numerically unusable. You can often work around that with a carefully chosen pre-conditioner, but you're rapidly going down a rabbit hole that takes you away from the extreme simplicity of conjugate-gradient.
- jmount 14y agoTrue. But this is all a rabbit hole. I think the upper comment was trying to point out that real linear algebra already has work from a trial vector methods of solution. So there is some precedent for non-factorization based solutions. But even that detracts that this really does seem to be a new method for finite fields.
- deleted 14y ago[deleted]
- colanderman 14y agoThis is very neat, in that it uses random combinations of vectors to maintain constant entropy over each iteration. Unfortunately this method does not improve on the O(n^2*m) asymptotic run-time of Gaussian elimination, nor does it address numerical stability issues (since it applies only to finite fields). Still neat though.
- bilbo0s 14y agoOK Cool. I thought I was just being dense until I came back to HN from the article and read this comment.
- rm999 14y agoI never took abstract algebra, can someone explain what is going on? I read about half the article before realizing I have no idea what they mean.
- ColinWright 14y agoAn answer to that depends a great deal on what you already know. If you know what linear equations are, and you know what a finite field is, then is seems pretty clear. Are you trying to "read like math" or are you trying to "read like a novel"? If you're interested then read it again, closely, trying to understand every sentence, then feel free to post here or email me with the first sentence you don't understand,
- rm999 14y agoI have a good applied math background, including linear algebra and gaussian elimination. First part I don't totally understand is: Prasad’s work is for solving linear systems over finite fields, specifically F_p, with p prime.
- eru 14y agoDo you know all the words in that sentence, and just can't seem how they work together to create meaning, or do you have problems with any specific word?
- ColinWright 14y agoRe-reading your question, since you are already familiar with linear algebra, the thing you need to know about is finite fields. But read the whole thing, it's in a logical progression. OK ... so a linear equation is one of the form: ax + by + ... + dz = n where the a, b, d and n are constants and the x, y, z, etc are the variables. You may be familiar with these when the constants are real numbers, but they can be from any field (more about that in a minute). An example of a linear equation is 3x + 5y - 2z = 1 So a system of linear equations is when you have lots of these. In large systems you may have literally millions of variables. So what's this about a "field"? Well, in general the constants don't need to be real numbers. There are properties that we want, such as addition, multiplication, subtraction and division, but there are systems that have these sorts of things that are not the real numbers. These are called fields. For example, the rational numbers have all the properties we might want. We can add, subtract, divide and multiply rationals, and things work the way we would want. But another example is the integers modulo 5. The numbers 0, 1, 2, 3 and 4 have all the properties we want. We can divide by 2, for example, but multiplying by 3, because 2x3=6, which is 1 (modulo 5). So we can have a field (a system with all the operations we want) that only has a finite number of elements. There are others, but the most common ones are to take the integers modulo some prime number. The proof that we get a field is not har, and is actually interesting, but some people find it tedious. So Prasad's work is for solving systems of linear equations where the constants are not real numbers, but come from a finite field. Finally, one of the most common finite fields in the area of computing is the field that has just two elements - 0 and 1. The other answers in this sub-thread are pretty good. Again, if you want to understand you will need to "read like math", but once you've done so, come and ask again if you have any questions.
- pmb 14y agoThis stuff has just been in the air the past few years - Network coding ( http://www.eecs.harvard.edu/~michaelm/CS222/contentdist.pdf http://www.eecs.harvard.edu/~michaelm/CS222/contentdist.pdf ) does the inverse operation to increase efficiency in Bittorrent-like distribution schemes. It is quite cool that randomness can help in both the creation and solving of these problems.
- beagle3 14y agoI wonder if there's an underlying "random attempts" theory that can tie these successes (that have intrigued me for a long time): 1. Shannon's random code book construction (for achieving the noisy channel rate limit) 2. Johnson-Lindenstrauss lemma http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_l..., the result that underlies most if not all of the compressive sensing field (and all of the recent superfast large scale SVD, PCA algorithms) And of course this recent result might also be related somehow.
- eru 14y agoThere's also the (bigger?) question whether randomness helps at all, e.g. whether P is weaker than P + a source of random bits. In practice, randomization does help, but like with P vs NP as far as I know nobody has proven anything definite.
- pmb 14y agoThe complexity classes that involve randomness have names like BPP, ZPP, and RP. BPP is usually the one people mean when they talk about practical problems that randomness might help solve. Although the second level of PH contains both NP and BPP, which both contain P, it is still not known if any of those containments are proper, and the relationship between BPP and NP is still open. Even more interesting is the relationship between BPP and its quantum version BQP. The Complexity Zoo has more for the interested reader... http://qwiki.stanford.edu/index.php/Complexity_Zoo http://qwiki.stanford.edu/index.php/Complexity_Zoo
- eru 14y agoThanks for giving a less hand-wavy account.
- azakai 14y ago> He starts with a random set of vectors {V_{0}}. Then he checks which ones satisfy the first equation. If the vectors are random, then about half of them will satisfy the equation. I don't follow this. Shouldn't it be 1/n, not 1/2?
- ColinWright 14y agoThey're using the specific example of GF(2) as the field. Any given assignment of values to variables then gives a value of 0 or 1, so there's a 50:50 chance of getting it right. If you're working over F_p then about 1/p of the randomly chosen vectors will satisfy the equation.
- azakai 14y agoThanks, I didn't realize it was a specific example there.
- propercoil 14y agoAnd no one mentioned a simple matrix?
- bascule 14y agoDoes this have any applications to elliptic curve cryptography?
- ColinWright 14y agoI suspect not. This technique works by assigning values to variables at random, lots of times, and then keeping the ones that happen to make the first equation true. You then somehow breed them into another large set, and winnow with the second equation. However, the number of elements in the fields involved there are so large that you need a huge number of equations to have even the smallest chance of any of them happening to be true "by chance", so I can't see how it could work as stated, but it's certainly an interesting question.