Mercurial > octave
diff libinterp/corefcn/svd.cc @ 22977:750c8b4b7164
Switch svd_driver to gesdd for performance (bug #49940).
* svd.cc (Vsvd_driver): Change static variable initialization to "gesdd".
* svd.cc (Fsvd): Add note to docstring about choice of algorithms and point to
svd_driver for more documentation.
* svd.cc (Fsvd_driver): Add discussion to docstring about choice of algorithms.
Change BIST test so that the original svd_driver is always restored even if the
test fails.
author | Rik <rik@octave.org> |
---|---|
date | Wed, 28 Dec 2016 15:33:34 -0800 |
parents | 5ff6716cf157 |
children | ef4d915df748 |
line wrap: on
line diff
--- a/libinterp/corefcn/svd.cc Wed Dec 28 17:49:02 2016 -0500 +++ b/libinterp/corefcn/svd.cc Wed Dec 28 15:33:34 2016 -0800 @@ -34,7 +34,7 @@ #include "utils.h" #include "variables.h" -static std::string Vsvd_driver = "gesvd"; +static std::string Vsvd_driver = "gesdd"; template <typename T> static typename octave::math::svd<T>::Type @@ -154,6 +154,13 @@ on the matrix @var{A}. If @var{A} has more rows than columns then an economy-sized decomposition is returned, otherwise a regular decomposition is calculated. + +Algorithm Notes: When calculating the full decomposition (left and right +singular matrices in addition to singular values) there is a choice of two +routines in @sc{lapack}. The default routine used by Octave is @code{gesdd} +which is 5X faster than the alternative @code{gesvd}, but may use more memory +and may be less accurate for some matrices. See the documentation for +@code{svd_driver} for more information. @seealso{svd_driver, svds, eig, lu, chol, hess, qr, qz} @end deftypefn */) { @@ -363,12 +370,39 @@ @deftypefnx {} {} svd_driver (@var{new_val}, "local") Query or set the underlying @sc{lapack} driver used by @code{svd}. -Currently recognized values are @qcode{"gesvd"} and @qcode{"gesdd"}. -The default is @qcode{"gesvd"}. +Currently recognized values are @qcode{"gesdd"} and @qcode{"gesvd"}. +The default is @qcode{"gesdd"}. When called from inside a function with the @qcode{"local"} option, the variable is changed locally for the function and any subroutines it calls. The original variable value is restored when exiting the function. + +Algorithm Notes: The @sc{lapack} library provides two routines for calculating +the full singular value decomposition (left and right singular matrices as +well as singular values). When calculating just the singular values the +following discussion is not relevant. + +The default routine use by Octave is the newer @code{gesdd} which is based on a +Divide-and-Conquer algorithm that is 5X faster than the alternative +@code{gesvd}, which is based on QR factorization. However, the new algorithm +can use significantly more memory. For an MxN input matrix the memory usage is +of order O(min(M,N) ^ 2), whereas the alternative is of order O(max(M,N)). In +general, modern computers have abundant memory so Octave has chosen to +prioritize speed. + +In addition, there have been instances in the past where some input matrices +were not accurately decomposed by @code{gesdd}. This appears to have been +resolved with modern versions of @sc{lapack}. However, if certainty is +required the accuracy of the decomposition can always be tested after the fact +with + +@example +@group +[@var{u}, @var{s}, @var{v}] = svd (@var{x}); +norm (@var{x} - @var{u}*@var{s}*@var{v'}, "fro") +@end group +@end example + @seealso{svd} @end deftypefn */) { @@ -384,9 +418,9 @@ %! [U1, S1, V1] = svd (A); %! svd_driver ("gesdd"); %! [U2, S2, V2] = svd (A); +%! svd_driver (old_driver); %! assert (U1, U2, 5*eps); %! assert (S1, S2, 5*eps); %! assert (V1, V2, 5*eps); -%! svd_driver (old_driver); */