9 ms·
When Double Precision Is Not Enough
- kkylin 5y agoFirst thought: the curve in that first plot reflects the pseudospectrum? (https://en.wikipedia.org/wiki/Pseudospectrum https://en.wikipedia.org/wiki/Pseudospectrum) Spectra of nonnormal matrices can be very hard to calculate accurately.
- mizzao 5y agoCame here expecting an article about Kahan summation, left having learned about a multiple-precision Python library...
- charlieyu1 5y agoSounds like bad algorithm.
- ogogmad 5y agoObligatory reference to computable analysis: https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis This shows that you can do exact real arithmetic without worrying about round-off errors. But it's expensive. If you want something more practical (but dodgy), you can use arbitrary-precision arithmetic instead of exact real arithmetic. To that end, there's the Decimal module in the Python standard lib. There's also the BC programming language which is part of POSIX. If you want to do matrix arithmetic, you can use mpmath for Python like they did in this blog post, or Eigen3 for C++ with an arbitrary-precision type. This is dodgy of course because the arithmetic remains inexact, albeit with smaller rounding errors than double-precision floats.
- midjji 5y agoThankfully someone figured out that quad should be in C++ a while back, unfortunately they didnt figure out that the next few dozen should be too... the arbitrary precision stuff is an alternative in theory, and would be if any of the hundreds of half completed projects to convert unintelligeble, and unmaintainable, unclear, etc, C to the in this specific case extremely much better C++ interfaces was complete.
- dekhn 5y agoIIUC most people instead precondition their matrices and stick to double precision instead of quad or deep precision.
- boulos 5y agoYeah, they also allude to "better ways to do it" both in the main text and the last paragraph: > The next post will discuss better ways to implement higher precision in numerical calculations. There are lots of automatic row / column swap techniques, particularly for sparse matrices that ensure you avoid catastrophic cancellation. You wouldn't do this automatically, because most matrices are reasonably conditioned (and figuring out the optimal swaps is NP complete and so on), but there are lots of algorithms to do well enough when you need to.
- jandrewrogers 5y agoThere are a few edge cases in geospatial computational geometry that require greater than quad precision to correctly compute a double precision result. This fact is sometimes used as a litmus test for implementation correctness. Many implementations don't have a conditional escape for these edge cases that switches to arbitrary precision algorithms in their double precision algorithms, which is easy to verify.
- nullc 5y agoThere is a flipside to this: e.g. GLIBC will switch to an arbitrary precision internal implementation for some operations that would otherwise lose a little precision and as a result run 1000x slower on some inputs. Not a good thing when you're attempting to do realtime signal processing.
- dekhn 5y agoI once wrote a "solar system simulator" in blender to generate images of solar eclipses from specific locations on earth. I modelled everything using meters, so literally placing the sun at the origin, and the earth at 1AU, and the moon near it. Turns out, blender uses single precision and the distance between earth and moon is incompatible with sun and earth, so all my renders were wrong. I divided all the sizes by 10 and it worked perfectly. As a counter argument, in my field of MD, it was eventually shown that most force field terms can be computed in single precision, with the exception of the virial expansion (https://en.wikipedia.org/wiki/Virial_stress https://en.wikipedia.org/wiki/Virial_stress) which has to be computed in DP.
- s1artibartfast 5y agoSimple but clever! I once spent a month debugging precision issues in custom python FEA code. Only after reading your post 10 years later do I realize I could have sidesteped the whole issue with a unit change. Doh XD!
- s2mcallis 5y agoI'd be interested in hearing if you have more info on this.
- peter303 5y agoThe are algorithms taught in numerical analysis class for re-ordering calculations to maximize precision. Computing in order you wrote on paper or the way you were initially taught may not be the best.
- vlmutolo 5y agoAn interesting tool to help preserve floating point precision is Herbie (https://herbie.uwplse.org/ https://herbie.uwplse.org/), which takes an expression as input and outputs an optimized version of it that will retain precision. The example they give on their site is: sqrt(x+1) - sqrt(x) => 1/(sqrt(x+1) + sqrt(x))
- klysm 5y agoThis tool is a really cool mix of hard math and soft reality. You need some pretty advanced tools to symbolically manipulate expressions like this, and then it takes the results and throws it on the wall to see what sticks best.
- dekhn 5y agodoes it generate erfc(x) from 1-erf(x)?
- vlmutolo 5y agoApparently it does. http://herbie.uwplse.org/demo/042341d0fe3004d56ba86a30344299e5e258e053.ea9754c765d6f2e3443236047de835c7bf56f0de/graph.html http://herbie.uwplse.org/demo/042341d0fe3004d56ba86a30344299...
- deleted 5y ago[deleted]
- gruez 5y agoI'm glad that there's a tool to automatically do this. When I was in university, this was something that was on tests/assignments.
- mistrial9 5y agouse 80 bits? https://en.wikipedia.org/wiki/Standard_Apple_Numerics_Environment https://en.wikipedia.org/wiki/Standard_Apple_Numerics_Enviro...
- liversage 5y agoOr 128 bits. FORTRAN has a REAL*16 type (quadruple precision floating point number). I encountered this at university in a physics department that studied non- linear systems also known as chaos theory. Rounding errors can quickly become a problem in these systems.
- gnufx 5y ago> FORTRAN has a REAL16 type Fortran (note the post-'77 spelling) doesn't. It has KINDs. REALx is a non-standard extension, and there's definitely no requirement to implement 128-bit floating point. I don't know what hardware other than POWER has hardware 128-bit FP (both IEEE and IBM format, with a somewhat painful recent change of the ppc64le ABI default in GCC etc.).
- thanatos519 5y agoGCC also has libquadmath which provides 128-bit floats by sticking 2 64-bit floats together. More than twice as slow, but extra precision just by changing a type and linking the library. Works great in XaoS, which is where I like my extra precision, but a deep fractal zoom can consume as much precision as you can muster. Imagine a 64kbit-precision Mandelbrot zoom!
- aragilar 5y agoThe main use of libquadmath seems to be to support gfortran. GCC/glibc also support _Float128 and <func>f128, which are nominally part of C, but only GCC implements them as far as I know.
- ip26 5y agoI believe x87 still offers 80 bits in your PC today.
- akimball 5y agoRational arithmetic needs better matrix libraries. No loss of precision then.
- klodolph 5y agoPeople have got to stop suggesting this. It doesn't make any sense and it's usually a waste of time. First of all, the example in the article is computing eigenvalues. Let me ask you: how do you expect to calculate eigenvalues using rational numbers? As a refresher, if it's been years since you took a look at linear algebra, the eigenvalues of a matrix are the roots of the matrix's characteristic polynomial, and we remember from high-school algebra that the roots of a polynomial are often not rational numbers, even if the coefficients are rational. Therefore, using rational arithmetic here is a complete non-starter. It's just not even possible, right from the very start. However, let's suppose that the particular problem that we are interested in solving does admit a rational solution. What then? Well, our real-world experience tells us that we often need an excessive amount computational resources and memory for exact, rational answers to linear algebra problems even of modest size. As you perform more computations on rational numbers, the memory required continues to grow.
- thechao 5y agoFloating point numbers are a particular way to represent (and modestly compress) rational numbers. I'm against rational number libraries because they use non-power-of-2 denominators and are, thus, fundamentally less efficient with respect to the actual cost of calculation.
- willis936 5y agoIf anyone ever runs out of precision using IIR filters: convert to second-order section (SOS). I stumbled upon this trick a few years ago and it's a game changer. No need for FIR.
- mochomocha 5y agoYep. The other advantages are that now you can parallelize compute, and you get lower latency.
- hcrisp 5y agoI found the same. I once computed a high-order (something like 100) low-pass Butterworth using SOS sections as a test and did not notice any instability in the filtered signal. The key was to directly derive the SOS coefficients using bilinear transformation.
- vHMtsdf 5y agoI remember a class I had where we were shown a methods for exact PC arithmetic with integers, rationals (e.g., 1/2) and algebraic numbers (e.g., sqrt(2)). Only thing it couldn't deal with were transcendental numbers (e.g., pi) I think it worked by representing the numbers by integer matrices, all operations were then matrix operations. Unfortunately, the matrices were gaining dimension when new algebraic numbers got involved, so it probably wasn't useful for anything :-). Anyway, it it blew me away anyway at the time, one of the few things that sticked with me from school.
- aSanchezStern 5y agoYeah there are a few number systems that can do this kind of thing, ranging from rational implementations where the numerator and denominator are stored, all the way to the computable reals (https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number), which can handle even trancendentals exactly! Fun fact, the built-in calculator on android actually uses the computable reals (https://dl.acm.org/doi/abs/10.1145/3385412.3386037 https://dl.acm.org/doi/abs/10.1145/3385412.3386037), so you can do any calculation on it, and then ask for any number of digits (keep scrolling the result), and it will always be correct. The only downside is that they're a little too slow to use in a lot of performance-sensitive numerical applications.
- frozenport 5y ago>> Numerically stable algorithms exist for such problems, but these occasionally fail leaving us to brute force the calculation with higher precision to minimize floating point rounding errors. Do algorithm authors really implement two code paths? One that uses a cost function iterative algorithm to solve the matrix (this is what everybody does), and a second algorithm using the brute force approach the author showed (known not to work).
- irchans 5y ago>> Do algorithm authors really implement two code paths? I do sometimes. Sometimes I test the result, and if it is not correct, then I use a slower, more numerically stable algorithm. I'm not sure if I have ever written code that repeats the same code with quad precision, but of course that would often work. Sometimes you can compute a correction from the "residual". >>One that uses a cost function iterative algorithm to solve the matrix (this is what everybody does), and a second algorithm using the brute force approach the author showed (known not to work). We do often use Jacobi or Gauss-Seidel, or something similar (esp for computing estimates of A^(-1)b ). In those cases we never revert back to QR. We do sometimes use Jacobi or GS to improve a result obtained from an ill conditioned QR, but rarely. Many years ago, I would have the code raise an exception if the result is bad so that I would get a call. When I got such a call, I would think about how to make the algorithm more stable.
- magicalhippo 5y agoThis reminded me of Posits[1] and Unums[2]. I dabbled with my own implementation some years ago, but nothing serious. Anyone tried them out? I see there's some FPGA implementations and a RISC-V extension idea[3], would be fun to try it on a softcore. [1]: https://posithub.org/docs/posit_standard.pdf https://posithub.org/docs/posit_standard.pdf [2]: http://johngustafson.net/unums.html http://johngustafson.net/unums.html [3]: https://www.posithub.org/khub_doc https://www.posithub.org/khub_doc
- aSanchezStern 5y agoUnfortunately while Posits (and Unums) are more accurate for some computations, they are still designed around using small numbers of bits to represent numbers, so they have error in computations just like floating point. The argument for posits are mostly that they produce less error on the inputs you care about, and more on the ones you don't, but it really depends on your computation; you really have to know what you're doing to use them safely.
- Dylan16807 5y agoWhich version? With current posits, they're a clever way to give more bits to precision near 1 and more bits to exponent near 0 and infinity, but if you're not overflowing or underflowing then it's a marginal improvement at best. Then Unum glues intervals on top, right? But you could do intervals with normal floats too. And you still won't get the correct answer, you'll just know the error exploded. Is the giant accumulator feature able to help here? For the other versions I tend to get completely lost.
- layer8 5y agoThere is a whole field about that, called numerical analysis: https://en.m.wikipedia.org/wiki/Numerical_analysis https://en.m.wikipedia.org/wiki/Numerical_analysis
- a-dub 5y agoalso worth noting that you can ask the fpu to trap to catch some types of precision loss or fp underflows.
- bayindirh 5y agoIf you're playing around subnormal numbers [0], most modern processors automatically switch to a microcode based calculation mode to preserve these numbers. However, these algorithms are very expensive, so it's not desired unless explicitly needed and generally used as an escape hatch for edge cases. [0]: https://en.wikipedia.org/wiki/Subnormal_number https://en.wikipedia.org/wiki/Subnormal_number
- mochomocha 5y agoRight, it's a very slow bandaid. If you're reaching subnormal numbers, it's usually a sign you're doing something wrong.
- a-dub 5y agoi'd be curious what matlab would do with finding the eigs for op's matrix. i'd bet a coffee that it (one of the eigs functions) prints a warning. entirely possible it may even switch search methods if precision loss is detected.
- mattkrause 5y agoI get the same results as the author if I pass the matrix to eig (R2020a, Intel Mac) >> lesp = gallery('lesp', 100) >> any(imag(eig(lesp))) ans = logical 0 >> any(imag(eig(lesp'))) ans = logical 1
- a-dub 5y agowhat about eigs() with the 'Display' option turned on?
- 5y ago
- bluetwo 5y agoI'll admit being lost in some of the math here but I wonder perhaps naively, if a language like Julia, which does fractions as fractions, would handle it better.
- salty_biscuits 5y agoIt's really just a floating point precision issue. Even if you represented the input matrix as a rational elementary type the output eigenvalues would be a subset of the reals and calculated as being floating point. You could get around it if you had a special matrix type where you knew you were definitely going to get rational eigenvalues and you could dispatch on that type.