5 ms·

I 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.

by rm999 14y ago

ColinWright 14y ago
An 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 ago
  I 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 ago
    Do 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 ago
    Re-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.
    - rm999 14y ago
      Oh, I see, that makes a lot of sense - thanks!
      - ColinWright 14y ago
        You're welcome.
  - deleted 14y ago
    [deleted]
  - csense 14y ago
    You've probably used Gauss-Jordan elimination over the reals. What properties of real numbers make Gauss-Jordan elimination work? The real numbers have addition and multiplication operations which each obey commutative, associative, identity, and inverse laws; and multiplication is distributes over addition. These properties are all that's required for Gauss-Jordan elimination to work. (We don't need other properties of real numbers, such as properties involving convergence of sequences, which you may have studied in calculus or real analysis class.) A set and binary operators + and * which have all of these properties, are called a "field" [1]. The real numbers, rational numbers, and complex numbers are probably your most familiar examples of fields. When talking about a field like "the field of rational numbers, Q", you're actually referring to a data structure (Q, +, *) which includes definitions of the addition and multiplication operators. Since most fields have "standard" addition and multiplication operators, often mathematicians drop them from discussion. Kind of like, when you're discussing a program with a colleague, you say, "Add the offset to the base," your colleague doesn't ask, "Add them as integers or floating-point numbers? What should I do if they overflow?" The answers to these questions are almost always clear from context, and also almost always near-universally standardized, at least within a particular programming language. Anyway, as other posters have noted, the integers modulo p, where p is prime, are actually a field. It's obvious that Z_p has most of the properties of a field, but multiplicative inverse is interesting. The proof of existence of multiplicative inverses mod p -- and a fast O(log(p)) implementation of finding them -- is the Euclidean algorithm, one of the oldest algorithms known to mankind. [2] [1] http://en.wikipedia.org/wiki/Field_%28mathematics%29 http://en.wikipedia.org/wiki/Field_%28mathematics%29 [2] http://en.wikipedia.org/wiki/Euclidean_Algorithm http://en.wikipedia.org/wiki/Euclidean_Algorithm
acomar 14y ago
A field is a structure that behaves very much like the reals (under the usual operations). That is, it's a set of elements with an addition operation with an identity called 0 (special elements are named after their numeric equivalents, but that doesn't mean they're always the same thing), a multiplication with an identity called 1, and the two interact "properly". That is, they distribute and the additive identity is the multiplicative zero. Further, inverses exist for all elements, with respect to both addition and multiplication (except 0). So very reals-like. Finite fields are then fields with a finite number of elements. Can you think of any examples? The easiest way to read the OP is to read the field F as if it were the reals, except with a finite number of elements. Let me know if that helps.
- sadga 14y ago
  Nit: A closer analogy is rationals, more so than reals (as reals have other unrelated properties like uncountability) That is, given your simple rings (the integers) and finite rings (modulo n), you get fields by introducing just division (integers -> rationals; mod-n -> mod-p for prime p).
dgreensp 14y ago
"F_p" means the field of integers modulo p. Fields have addition and multiplication. If p is prime, the integers mod p have nice properties, like every one has an inverse. For example, F_7 is the finite field of 0,1,2,3,4,5,6. You can add and multiply these (mod 7): 6 + 2 == 1, 2 * 5 == 3. The elements 0 and 1 work as you'd expect to satisfy the usual identities of arithmetic. Additionally, every element except 0 has a multiplicative inverse. 1 * 1 == 1, 2 * 4 == 1, 3 * 5 == 1, and 6 * 6 == 1. To "divide" by 2, you just multiply by 4. Etc.
jastr 14y ago
Here goes: You think that Microsoft's stock price is directly related to how much it rained in Seattle. So you look at one day and see it rained 10 inches and the stock price was $20. On the next day, it rained 6 inches and the stock price fell to $12. What's the relationship between rain and stock price? Obviously 2x. How would your figure that out mathematically? (Inches of rain) * ( relationship ) = ( stock price ) So we must find a relationship ( we'll call it r) that works for both of these equations (10)(r) = 20 (6)(r) = 12 Obvs r=2. That was easy. What if you think this is too simple and the stock price is actually related to both rain fall and the temperature. We need a new equation (Inches of rain)(relationship 1) + (temperature)(relationship 2) = ( stock price ) Relationship 1 and relationship 2 are different values, because maybe rain has a much bigger impact on the stock price than temperature. So we need to solve for r1 and r2. (Try making up numbers for rain, temperature, and price on 3 days, and you'll find this gets ugly to solve.) Then you decide again this is too simple, and the stock price replies on rain, temperature, the moons distance from the earth, the amount of red cars you see on the way to work, etc. Now we have a lot of big equations, that we'd like to solve. Once we solve them we can determine the relationships each factor has on the stock price and tomorrow we can look at all the inputs (temperature, rainfall, etc) and predict the stock price. Matrices are a way of representing all these equations at once. Matrices are just a data structure, a way of representing equations. Just like computer data structures, matrices have certain functions that you can perform on them, like adding or multiplying them with other matrices. There are lots of applications that use really really big matrices with thousands of inputs and we'd like to solve these matrices ( ie. find the relationships ). There are a lot of ways of solving this, like Gauss-Jordan Elimination (which you probably know how to do even if you don't know that you know how). The problem is that most of these algorithms are very slow, because they perform lots of computations manipulating the matrices in order to solve them. (I have to get back to work so the rest is real short.) In short, this new algorithm is just a really clever guess and check, sort of like genetic algorithms. The algorithm guesses possible values for each relationship. If a set of relationships (aka a vector) fits some of the equations (but not all), then the algorithm generates more relationships similar to it. This goes on until the algorithm finds a set of values for relationships that work in each equation.

I 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.

by rm999 14y ago

I 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 ago

An 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 ago
I 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 ago
  Do 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 ago
  Re-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.
  - rm999 14y ago
    Oh, I see, that makes a lot of sense - thanks!
    - ColinWright 14y ago
      You're welcome.
- deleted 14y ago
  [deleted]
- csense 14y ago
  You've probably used Gauss-Jordan elimination over the reals. What properties of real numbers make Gauss-Jordan elimination work? The real numbers have addition and multiplication operations which each obey commutative, associative, identity, and inverse laws; and multiplication is distributes over addition. These properties are all that's required for Gauss-Jordan elimination to work. (We don't need other properties of real numbers, such as properties involving convergence of sequences, which you may have studied in calculus or real analysis class.) A set and binary operators + and * which have all of these properties, are called a "field" [1]. The real numbers, rational numbers, and complex numbers are probably your most familiar examples of fields. When talking about a field like "the field of rational numbers, Q", you're actually referring to a data structure (Q, +, *) which includes definitions of the addition and multiplication operators. Since most fields have "standard" addition and multiplication operators, often mathematicians drop them from discussion. Kind of like, when you're discussing a program with a colleague, you say, "Add the offset to the base," your colleague doesn't ask, "Add them as integers or floating-point numbers? What should I do if they overflow?" The answers to these questions are almost always clear from context, and also almost always near-universally standardized, at least within a particular programming language. Anyway, as other posters have noted, the integers modulo p, where p is prime, are actually a field. It's obvious that Z_p has most of the properties of a field, but multiplicative inverse is interesting. The proof of existence of multiplicative inverses mod p -- and a fast O(log(p)) implementation of finding them -- is the Euclidean algorithm, one of the oldest algorithms known to mankind. [2] [1] http://en.wikipedia.org/wiki/Field_%28mathematics%29 http://en.wikipedia.org/wiki/Field_%28mathematics%29 [2] http://en.wikipedia.org/wiki/Euclidean_Algorithm http://en.wikipedia.org/wiki/Euclidean_Algorithm

acomar 14y ago

A field is a structure that behaves very much like the reals (under the usual operations). That is, it's a set of elements with an addition operation with an identity called 0 (special elements are named after their numeric equivalents, but that doesn't mean they're always the same thing), a multiplication with an identity called 1, and the two interact "properly". That is, they distribute and the additive identity is the multiplicative zero. Further, inverses exist for all elements, with respect to both addition and multiplication (except 0). So very reals-like. Finite fields are then fields with a finite number of elements. Can you think of any examples? The easiest way to read the OP is to read the field F as if it were the reals, except with a finite number of elements. Let me know if that helps.

sadga 14y ago
Nit: A closer analogy is rationals, more so than reals (as reals have other unrelated properties like uncountability) That is, given your simple rings (the integers) and finite rings (modulo n), you get fields by introducing just division (integers -> rationals; mod-n -> mod-p for prime p).

dgreensp 14y ago

"F_p" means the field of integers modulo p. Fields have addition and multiplication. If p is prime, the integers mod p have nice properties, like every one has an inverse. For example, F_7 is the finite field of 0,1,2,3,4,5,6. You can add and multiply these (mod 7): 6 + 2 == 1, 2 * 5 == 3. The elements 0 and 1 work as you'd expect to satisfy the usual identities of arithmetic. Additionally, every element except 0 has a multiplicative inverse. 1 * 1 == 1, 2 * 4 == 1, 3 * 5 == 1, and 6 * 6 == 1. To "divide" by 2, you just multiply by 4. Etc.

jastr 14y ago

Here goes: You think that Microsoft's stock price is directly related to how much it rained in Seattle. So you look at one day and see it rained 10 inches and the stock price was $20. On the next day, it rained 6 inches and the stock price fell to $12. What's the relationship between rain and stock price? Obviously 2x. How would your figure that out mathematically? (Inches of rain) * ( relationship ) = ( stock price ) So we must find a relationship ( we'll call it r) that works for both of these equations (10)(r) = 20 (6)(r) = 12 Obvs r=2. That was easy. What if you think this is too simple and the stock price is actually related to both rain fall and the temperature. We need a new equation (Inches of rain)(relationship 1) + (temperature)(relationship 2) = ( stock price ) Relationship 1 and relationship 2 are different values, because maybe rain has a much bigger impact on the stock price than temperature. So we need to solve for r1 and r2. (Try making up numbers for rain, temperature, and price on 3 days, and you'll find this gets ugly to solve.) Then you decide again this is too simple, and the stock price replies on rain, temperature, the moons distance from the earth, the amount of red cars you see on the way to work, etc. Now we have a lot of big equations, that we'd like to solve. Once we solve them we can determine the relationships each factor has on the stock price and tomorrow we can look at all the inputs (temperature, rainfall, etc) and predict the stock price. Matrices are a way of representing all these equations at once. Matrices are just a data structure, a way of representing equations. Just like computer data structures, matrices have certain functions that you can perform on them, like adding or multiplying them with other matrices. There are lots of applications that use really really big matrices with thousands of inputs and we'd like to solve these matrices ( ie. find the relationships ). There are a lot of ways of solving this, like Gauss-Jordan Elimination (which you probably know how to do even if you don't know that you know how). The problem is that most of these algorithms are very slow, because they perform lots of computations manipulating the matrices in order to solve them. (I have to get back to work so the rest is real short.) In short, this new algorithm is just a really clever guess and check, sort of like genetic algorithms. The algorithm guesses possible values for each relationship. If a set of relationships (aka a vector) fits some of the equations (but not all), then the algorithm generates more relationships similar to it. This goes on until the algorithm finds a set of values for relationships that work in each equation.