search

stillwater-sc / universal

Large collection of number systems providing custom arithmetic for mixed-precision algorithm development and optimization for AI, Machine Learning, Computer Vision, Signal Processing, CAE, EDA, control, optimization, estimation, and approximation.
MIT License
404 stars 59 forks source link

SVD with posits #248

Open touisteur opened 3 years ago

touisteur commented 3 years ago

Hi,

Looking through the codebase, it seems the SVD function is all commented, while the Jacobi solver isn't. Can I perform a SVD on a square posit matrix using universal, yet? How would i go from (for example) a 3x3 single precision to a 3x3 (32,2 for example) posit one? Any numbers on the performance of SVD/Jacobi on posits on CPU/GPU? Would the use of posits help to converge faster and/or more precisely?

Thanks in advance.

Ravenwater commented 3 years ago

The best way to get linear algebra is by using MTL (https://github.com/simunova/mtl4) or Eigen and use their algorithms. These environments support sparse linear algebra and thus are much better suited to run linear algebra reproducibility and accuracy experiments. MTL and Eigen both offer parameterized interfaces so you can present them with posits and they will do the non-FDP forms of linear algebra.

We have done lots of convergence and precision tests to contrast posits with floats and doubles, and in general, posits will beat floats of the same size. But we want the 2-4x benefit, so we want a posit<16,2> beat a double. And for that you really need the fused dot product. And MTL is the only environment that has FDP enabled some linear algebra operators. We do not have yet an FDP enabled SVD or eigenvalue solver, and we are working to provide just dense matrix versions in Universal so that folks can experiment inside Universal and not have to install environments like Eigen to get a taste.

What we discovered though is that convergence is more algorithm and data-dependent than number system dependent. A good preconditioner will speed convergence orders of magnitude, whereas number systems are in the 10-20% range, 2x if you bring in user-defined rounding via FDP. So you would first need to find the right preconditioner before you could do a proper convergence comparison between number systems.

This is a very rich area of research opportunities though. Ping me if you want to learn more what research is currently in flight.