6 ms·
Can We Solve Linear Algebra Problems at Extreme Scale and Low Precisions?
- thxg 5y agoThe article covers ways to obtain smaller error bounds, mainly for testing algorithm stability in practice. The methods proposed are very varied in nature: blocked algorithms, x87 80-bit arithmetic, AVX2/ARMv8-A fused multiply-add (FMA) operations, and probabilistic bounds. While the article is otherwise very good, I am unsure about one of those in 2021: 80-bit arithmetic. The corresponding x87 instructions are deprecated by Intel, and their performance is disastrous. For example, the complex algorithms implemented in software by glibc to compute transcendental functions (sin, cos, exp, ...) are faster and more accurate than their single instruction x87 FPU counterparts (FSIN, FCOS, ...)! I would be very curious to see, in a few algorithms, a comparison of x87 arithmetic with double-doubles and even low-precision MPFR. MPFR, by the way, may have its place here if we're talking about sacrificing some performance for higher precision.
- gpderetta 5y agoThe trascendental instructions are slow and have low accuracy, but the "normal" x87 fp ops are still fast (except for the lack of vectorization).
- thxg 5y agoYou're right, I didn't know that. In a quick "long double" vs "double" microbenchmark, I see a negligible penalty for additions and comparisons, and 37% penalty when multiplications are involved.
- adgjlsfhk1 5y agoYeah. The problem with them is that using double-double based methods gives you 104 bits of precision that works with vectorization (and therefore is faster than x87).
- gpderetta 5y agoI assume double-double would be the emulated __float128 type in GCC (or hand written equivalent)? Can GCC vectorize it or it needs to be done by hand?
- snovv_crash 5y agoAgreed, I've seen better results from algorithmic approaches. For example, Takahashi for bounded-error on extremely large dot product. Depending on use case even doing a pseudo-Takahashi where you only merge the error back once every N iterations can unblock instruction-level parallelism letting the performance hit be only around 2x relative to naive dot products, but with still effectively the same guarantees.
- evancox100 5y agoI think they were only recommending x87 for a final summation
- ddmd 5y agoOne interesting question is how to implement linear algebra for the case of binary variables x_i in {0,1} or x_i in {-1,0,+1} as opposed to having continuous variables. Of course, it will be somewhat different theory but the general properties should be analogous to those of standard linear algebra. For example, dot product should express the notion of orthogonality, there should be well defined distance etc. I am not sure that such a theory exists at all but if yes then I am curious if there exist implementations.
- yobbo 5y agoYou might find what you're looking for if you google "linear systems over finite fields" or "integer linear systems".
- tlarkworthy 5y agoMixed integer programming? Here is a browser version https://observablehq.com/@tomlarkworthy/mip https://observablehq.com/@tomlarkworthy/mip
- tryingtopost 5y agoIt exists. Linear algebra is defined over finite fields. In the case of {0, 1} that is Z_2 and the case of { -1, 0, + 1 } that is Z_3.
- ouid 5y agoThere are algorithms which fail over GF(2). Gram-schmidt, for instance.
- dragontamer 5y agoDiscrete mathematics theory is possibly more difficult than the set of complex numbers. Case in point: linear optimization across the reals/complex field is solved with the simplex algorithm. Boolean optimization in contrast, is NP-complete since its equivalent to the knapsack problem (0 for "don't pack the object" and 1 for "do pack the object". Each object has a space it takes up + a value. Optimizing on value is NP-complete). Literally more difficult from a computational perspective than its Real/Complex analogue, and __provably__ so. I'm enjoying my personal studies into Binary Decision Diagrams: the data-structures that are used in Verilog / VHDL synthesizers, libraries, CPU-design, verification (etc. etc.) to encode boolean truth tables and yes... tackle NP-complete and even #P-complete problems (#P complete is "determine the number of solutions" to an NP complete problem. Knights Tours aren't NP complete but... see the paper for an example of #P-like counting problems: "The Number of Knight's Tours Equals 33,439,123,484,294": https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.528&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45...). The boolean truth table for a 64x64-bit multiplication is 128-bits of input and 128-bits of output. That's 2^253 bytes of storage under a naive scheme, which is clearly unworkable. Binary Decision Diagrams make it possible to store, compute, and "think" about these functions at a high level. (Ex: counting solutions, finding the 1st solution, combining truth tables together, etc. etc.) Knuth's TAOCP Volume 4A has been a good introduction to the theory, but Knuth's writing style is so difficult sometimes. I'm probably going to buy a supplemental textbook on the subject...
- knuthsat 5y agoI wonder how does this affect deep learning calculations and how it's possible that all those multiplications and additions still work.
- mturmon 5y agoHigham's writing is very readable and his book on numerical linear algebra is approachable and has information that's hard to find elsewhere. His point about probabilistic error bounds for roundoff errors is excellent! The usual bounds are worst-case, and assume all roundoff errors complement each other. That doesn't happen in practice: the errors average out -- it's readily observable. As Higham points out, this means intuitively that error magnitudes go from O(n) to O(sqrt(n)) which is huge for large n. I wasn't aware of his very recent joint work with Theo Mary that proves this under some conditions.
- techbio 5y agoI've heard the phenomenon from your second paragraph called "the miracle of mitigating errors" in the context of old-school (pre-GPS) transoceanic navigation.