5 ms·

An algorithm for "matrix multiplication" that assumes infinite precision arithmetic is used is essentially useless (there are some niche uses for matrices with

An algorithm for "matrix multiplication" that assumes infinite precision arithmetic is used is essentially useless (there are some niche uses for matrices with entries in finite fields/rings). An algorithm for matrix multiplication usually comes with more than that, in particular some sort of error bound. Note that these bounds are mathematical, part of the abstract algorithm, and not something that is a property of any particular implementation (your last paragraph suggests you might be confused by this). You want a statement that says if A' is close to A (in some relevant distance measure), and B' is close to B, then your algorithm gives something close to AB. The correctness you have to prove includes proving that your error bounds are what you say they are.

DannyBee 4y ago
Again, useless is not the same as incorrect. It is still correct whether it can be used somewhere due to implementation limitations or not. I'm really unsure how you can possibly argue otherwise. It's like arguing that a string algorithm is incorrect because it doesn't run fast enough on strings to be usable on any current computer. It's still correct. It's just not usable. Unlike correctness, useless is very context specific. 100 years from now, an infinite precision arithmetic algorithm may be entirely useful.
- eigenket 4y ago
  I am arguing that a matrix multiplication algorithm, like essentially any other numerical algorithm, consists of (at least) the following two parts 1. The actual steps you have to follow. 2. Some form of error bounds/analysis that tell you how good/bad the output will be given approximate inputs. In order to prove correctness you have to prove that the procedure gives the error bounds you claim. The error bounds are something you mathematically have to prove.
  - adgjlsfhk1 4y ago
    There are lots of methods (e.g. LU) that are used millions of times a day, but don't have good error bounds. Most matrix algorithms used in practice have something resembling a proof of error bounds that everyone ignores because they don't do a good job of describing the error that you actually get when you use the methods.
  - DannyBee 4y ago
    "In order to prove correctness you have to prove that the procedure gives the error bounds you claim" You don't get to just add your own requirement for correctness and then force people to prove it? They claim a specific thing - they prove that thing. That thing suffices to prove that it succeeds at matrix multiplication. You for some reason really just don't like that as far as i can tell, and argue it doesn't suffice for usefulness (which i agree on) Matrix multiplication, and "essentially any other numerical algorithm", is not defined in terms of the error bounds for correctness. That is just BS. The error bounds depend on implementation factors, and as such, they are totally unrelated to correctness. Let's take a look: https://en.wikipedia.org/wiki/Matrix_multiplication https://en.wikipedia.org/wiki/Matrix_multiplication I have read the entire definition, nowhere does it refer to error bounds as a requirement for successful matrix multiplication! The word "error" does not even appear on the page Since it's wikipedia, I also pulled out my college math books. Same thing. They prove correctness without any reference to error bounds. Those are accepted proofs. I don't see a single basic proof that has error bounds as part of correctness. It, again, wouldn't make any sense, because error bounds depend on implementation factors. So again, you simply can't add your requirement to correctness just because you like it. They still remain where they should be - usefulness for application.
    - eigenket 4y ago
      You seem to be confusing the mathematical definition of matrix multiplication with an explicit algorithm to compute it. The wiki page you linked is almost entirely about the abstract mathematical definition and talks about algorithms only for a single paragraph, which is about computational complexity. If you look at the wiki page for a particular algorithm (e.g. Strassen: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm) then of course they talk about stability in comparison to the naive algorithm (although the page could be improved quite a bit). If your college textbooks do not mention error analysis, conditioning and stability then they are not numerical linear algebra books worthy of the name. Check out a reference like Trefethen and Bau's Numerical Linear Algebra for example. This book has a whole part (out of the 7 parts in the book) talking about conditioning and stability, and these ideas are present throughout other parts as well. Once more the type of analysis I'm talking about is emphatically not implementation dependent. It is a property of the algorithm itself. For an example of the sort of statement I mean check out theorem 3.1 of this paper: https://arxiv.org/abs/math/0603207 https://arxiv.org/abs/math/0603207. If you disagree with me then please indicate what sort of "implementation factors" appear in the statement of the theorem.
- topaz0 4y ago
  What does "correctness" mean? It's impossible to talk about correctness without specifying what you are intending to compute. Numerical algorithms frequently have correctness conditions specified in terms of a precision (e.g. compute a floating point approximation to f(x) to within 1eps), and any algorithm that doesn't meet that precision is incorrect with respect to that correctness condition, by definition. So you can think of this paper as saying "suppose you have a correct multiplication and addition operation on the field of interest. Then this algorithm for multiplying matrices over that field, which is composed of a sequence of those multiply and add operations, computes the correct matrix product." That is a perfectly provable kind of fact, that as you say doesn't stop being the case if you switch computers or something. But fpmul and fpadd on your computer doesn't satisfy the condition for this proof! Therefore it doesn't apply, except by rough analogy. Then, other people might be interested in a different kind of proof, of a fact more like: "given two matrices of floating point numbers and fpmul and fpadd operations that are within .5eps precision, this sequence of fpmul and fpadd operations provably computes the matrix product such that the eigenvalues of the product are within .5eps of the true values". (edit to add: you could then also prove that the implementations of fpmul and fpadd on your computer satisfy the first condition, or replace them with implementations that do). That is also a well-specified correctness condition, and it is a correctness condition that is not necessarily satisfied by replacing "multiply" and "add" in the first algorithm with "fpmul" and "fpadd". This is what it means for "correctness [to be] context dependent". It doesn't invalidate the first proof, it just means we are interested in a different correctness condition than the first proof proves. (edit to format, and add: of course different conditions on precision are relevant to different applications. Maybe I need my matrix elements to be computed within some absolute error bound, but my friend needs them computed within a relative error bound. Or I need it to be able to work on subnormal numbers within a certain precision, but my friend only needs it to be precise for numbers between 1 and 2. Different algorithms may satisfy one condition but not the other.)
  - eigenket 4y ago
    Thanks for this comment. I think I started in this comment section trying to say something like this, but said it in a bad way, and then got progressively more confused and less clear in my responses as the day went on. This is much more clear than anything I would have been able to write.

DannyBee 4y ago

Again, useless is not the same as incorrect. It is still correct whether it can be used somewhere due to implementation limitations or not. I'm really unsure how you can possibly argue otherwise. It's like arguing that a string algorithm is incorrect because it doesn't run fast enough on strings to be usable on any current computer. It's still correct. It's just not usable. Unlike correctness, useless is very context specific. 100 years from now, an infinite precision arithmetic algorithm may be entirely useful.

eigenket 4y ago
I am arguing that a matrix multiplication algorithm, like essentially any other numerical algorithm, consists of (at least) the following two parts 1. The actual steps you have to follow. 2. Some form of error bounds/analysis that tell you how good/bad the output will be given approximate inputs. In order to prove correctness you have to prove that the procedure gives the error bounds you claim. The error bounds are something you mathematically have to prove.
- adgjlsfhk1 4y ago
  There are lots of methods (e.g. LU) that are used millions of times a day, but don't have good error bounds. Most matrix algorithms used in practice have something resembling a proof of error bounds that everyone ignores because they don't do a good job of describing the error that you actually get when you use the methods.
- DannyBee 4y ago
  "In order to prove correctness you have to prove that the procedure gives the error bounds you claim" You don't get to just add your own requirement for correctness and then force people to prove it? They claim a specific thing - they prove that thing. That thing suffices to prove that it succeeds at matrix multiplication. You for some reason really just don't like that as far as i can tell, and argue it doesn't suffice for usefulness (which i agree on) Matrix multiplication, and "essentially any other numerical algorithm", is not defined in terms of the error bounds for correctness. That is just BS. The error bounds depend on implementation factors, and as such, they are totally unrelated to correctness. Let's take a look: https://en.wikipedia.org/wiki/Matrix_multiplication https://en.wikipedia.org/wiki/Matrix_multiplication I have read the entire definition, nowhere does it refer to error bounds as a requirement for successful matrix multiplication! The word "error" does not even appear on the page Since it's wikipedia, I also pulled out my college math books. Same thing. They prove correctness without any reference to error bounds. Those are accepted proofs. I don't see a single basic proof that has error bounds as part of correctness. It, again, wouldn't make any sense, because error bounds depend on implementation factors. So again, you simply can't add your requirement to correctness just because you like it. They still remain where they should be - usefulness for application.
  - eigenket 4y ago
    You seem to be confusing the mathematical definition of matrix multiplication with an explicit algorithm to compute it. The wiki page you linked is almost entirely about the abstract mathematical definition and talks about algorithms only for a single paragraph, which is about computational complexity. If you look at the wiki page for a particular algorithm (e.g. Strassen: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm) then of course they talk about stability in comparison to the naive algorithm (although the page could be improved quite a bit). If your college textbooks do not mention error analysis, conditioning and stability then they are not numerical linear algebra books worthy of the name. Check out a reference like Trefethen and Bau's Numerical Linear Algebra for example. This book has a whole part (out of the 7 parts in the book) talking about conditioning and stability, and these ideas are present throughout other parts as well. Once more the type of analysis I'm talking about is emphatically not implementation dependent. It is a property of the algorithm itself. For an example of the sort of statement I mean check out theorem 3.1 of this paper: https://arxiv.org/abs/math/0603207 https://arxiv.org/abs/math/0603207. If you disagree with me then please indicate what sort of "implementation factors" appear in the statement of the theorem.
topaz0 4y ago
What does "correctness" mean? It's impossible to talk about correctness without specifying what you are intending to compute. Numerical algorithms frequently have correctness conditions specified in terms of a precision (e.g. compute a floating point approximation to f(x) to within 1eps), and any algorithm that doesn't meet that precision is incorrect with respect to that correctness condition, by definition. So you can think of this paper as saying "suppose you have a correct multiplication and addition operation on the field of interest. Then this algorithm for multiplying matrices over that field, which is composed of a sequence of those multiply and add operations, computes the correct matrix product." That is a perfectly provable kind of fact, that as you say doesn't stop being the case if you switch computers or something. But fpmul and fpadd on your computer doesn't satisfy the condition for this proof! Therefore it doesn't apply, except by rough analogy. Then, other people might be interested in a different kind of proof, of a fact more like: "given two matrices of floating point numbers and fpmul and fpadd operations that are within .5eps precision, this sequence of fpmul and fpadd operations provably computes the matrix product such that the eigenvalues of the product are within .5eps of the true values". (edit to add: you could then also prove that the implementations of fpmul and fpadd on your computer satisfy the first condition, or replace them with implementations that do). That is also a well-specified correctness condition, and it is a correctness condition that is not necessarily satisfied by replacing "multiply" and "add" in the first algorithm with "fpmul" and "fpadd". This is what it means for "correctness [to be] context dependent". It doesn't invalidate the first proof, it just means we are interested in a different correctness condition than the first proof proves. (edit to format, and add: of course different conditions on precision are relevant to different applications. Maybe I need my matrix elements to be computed within some absolute error bound, but my friend needs them computed within a relative error bound. Or I need it to be able to work on subnormal numbers within a certain precision, but my friend only needs it to be precise for numbers between 1 and 2. Different algorithms may satisfy one condition but not the other.)
- eigenket 4y ago
  Thanks for this comment. I think I started in this comment section trying to say something like this, but said it in a bad way, and then got progressively more confused and less clear in my responses as the day went on. This is much more clear than anything I would have been able to write.