2
$\begingroup$

I have a real square matrix $X$ which I need to perform a Singular Value Decomposition on. Now, performing the operation

$$ X = USV^T $$

as $U$ and $V$ are orthogonal, we know that $\det(X)=\pm\det(S)$ and $\det(S)$ is non-negative as singular values are non-negative.

Now, I need to know the sign of the determinants of $U$ and $V$ (which is the same as knowing the determinants, of course). However, the naive approach costs me $2 O(N^3)$

I was wondering whether someone knows of a way to either

  1. Infer the sign of the determinants of $U$ and $V$ as a bi-product of the SVD-implementation in numpy,scipy or a similar library in Python, without having to call det(U) and det(V).
  2. Calculate the determinant of an orthogonal matrix that is faster than the default implementation of det(U), based on the fact that $U/V$ is orthogonal.

PS: prior question on Stack Overflow.

$\endgroup$
5
  • 1
    $\begingroup$ Are you looking for a pure python implementation? There is some potential to infer the determinants as a by product of the svd in numpy, but that library internally calls some Fortran code, and you would have to dig around in that code. $\endgroup$ Nov 9 '21 at 7:15
  • 1
    $\begingroup$ @ThijsSteel I'd be curious to hear about this approach, regardless of its Python purity. $\endgroup$ Nov 9 '21 at 16:29
  • $\begingroup$ Out of interest, what is this for? Is the determinant of the svd factors commonly used in your field? $\endgroup$ Nov 10 '21 at 16:54
  • $\begingroup$ @ThijsSteel Technically, I do not need the determinants of the $U$ and $V$-matrices, but a decomposition $X=U'\Sigma'(V^T)'$ where $det(V')=det(U')=1$, $U'$ and $V'$ unitary and $\Sigma'$ diagonal (but it may have negative entries) - so it's a "modified SVD". But by knowing the determinants of $U$ and $V$ in a standard SVD, I know whether or not I need to switch a sign of a column/row in the unitary matrices and $\Sigma$ to get what I need. I work with Quantum Chemistry, and I need this decomposition to calculate the overlap/matrix elements of two nonorthgonal Slater Determinants efficiently. $\endgroup$
    – cheetah
    Nov 14 '21 at 15:59
  • $\begingroup$ Very interesting use case. It would surprise me if you managed to get good speedups though. The determinant is usually calculated using the LU factorization. Even though LU's O(n^3) asymptotic cost is the same as the SVD. The LU is usually way way faster. If you're already doing an SVD, optimizing those LU's away won't do that much, but every little bit counts I guess and it was still fun to do. $\endgroup$ Nov 16 '21 at 9:27
6
$\begingroup$

If you are prepared to go digging around in the fortran code:

The SVD algorithm consists of a few parts:

  1. Bidiagonalization (usually using Householder reflectors)
  2. Use QR shifts to reduce the bidiagonal to diagonal (usually using Givens rotations)
  3. Change the sign of any negative diagonal elements and reorder the singular values so the are decreasing.

Notation clarification, I write the SVD as $A = USV^T$.

A reflector typically has determinant -1, so applying one will change the sign of the determinant. A small detail, LAPACK sometimes "cheats" and uses a trivial rotation instead of a reflector, this is if a specific column is already reduced. To calculate the determinant after step one, simply count the number of nontrivial reflectors for both $U$ and $V$. If there are $k$ nontrivial reflectors, the determinant is $(-1)^k$.

A rotation has determinant 1, so applying one will not change the sign of the determinant. As a consequence, we do not need to take the calculations in step 2 into account.

To change the sign of the diagonal elements, LAPACK multiplies the corresponding column in $V$ by $-1$, this also changes the sign of the determinant of $V$ again. So similarly to the reflectors, we need to count the number of sign changes to get the determinant up to this point.

To reorder the singular values, we also need to reorder both $U$ and $V$, each swap will change the sign of the determinant. Again, we count the number of swaps.

It is possible that i missed some detail, i'm more familiar with eigenvalue solvers than the specialized svd routine.

$\endgroup$
3
  • 1
    $\begingroup$ This is a great answer, but possibly not "operative" enough. I'd add something on the lines of "you'll need to manually change the Lapack (Fortran) code and add a further parameter to several functions. This parameter takes the value $\pm 1$. You want to flip its sign every time you apply a Householder reflector (after checking that the reflector is not the trivial one) or normalize eigenvalue blocks". $\endgroup$ Nov 10 '21 at 7:51
  • $\begingroup$ Good point, i'll add some more details when I have time. $\endgroup$ Nov 10 '21 at 15:19
  • $\begingroup$ Clever idea! +1 $\endgroup$ Nov 11 '21 at 2:40
5
$\begingroup$

For part 1: To my knowledge, the answer is no.

For part 2: This question had several good answers, all of which were negative (there isn't really a faster way). I don't believe there is meaningful new literature on the topic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.