= Menu

Computing the Singular Value Decomposition of 3x3 matrices with minimal branching and elementary floating point operations

Aleka McAdams, Andrew Selle, Rasmus Tamstorf, Joseph Teran, Eftychios Sifakis
Technical Report , University of Wisconsin - Madison — May 2011
    Download the publication : SVD_TR1690.pdf [386Ko]  
    A numerical method for the computation of the Singular Value Decomposition of 3 x 3 matrices is presented. The proposed methodology robustly handles rank-de?cient matrices and guarantees orthonormality of the computed rotational factors. The algorithm is tailored to the characteristics of SIMD or vector processors. In particular, it does not require any explicit branching beyond simple conditional assignments (as in the C++ ternary operator ?:, or the SSE4.1 instruction VBLENDPS), enabling trivial data-level parallelism for any number of operations. Furthermore, no trigonometric or other expensive operations are required; the only ?oating point operations utilized are addition, multiplication, and an inexact (yet fast) reciprocal square root which is broadly available on current SIMD/vector architectures. The performance observed approaches the limit of making the 3 x 3 SVD a memory-bound (as opposed to CPU-bound) operation on current SMP platforms.

    Images and movies

     

    BibTex references

    @TechReport{MSTTS11,
      author       = "McAdams, Aleka and Selle, Andrew and Tamstorf, Rasmus and Teran, Joseph and Sifakis, Eftychios",
      title        = "Computing the Singular Value Decomposition of 3x3 matrices with minimal branching and elementary floating point operations",
      institution  = "University of Wisconsin - Madison",
      month        = "May",
      year         = "2011",
      type         = "technical report",
      url          = "http://graphics.cs.wisc.edu/Papers/2011/MSTTS11"
    }
    
     

    Other publications in the database