Tag Info

0

I solved the problem by computing the eigenvalue with smallest magnitude with ARPACK. Is this correct?

2

@Federico Poloni 's fine answer states the impossibility of getting an exact yes/no answer using IEEE arithmetic. However, using interval arithmetic with outward rounding, it is possible to get a "not singular/don't know" answer. In particular, it may be possible to definitively conclude that the smallest singular value is strictly greater than ...

2

I also suggest looking into the condition number estimators, which will (with some degree of [un]reliability) predict how effectively numerically singular the matrix is. In particular, "Spectral Condition-Number Estimation of Large Sparse Matrices" based on LSQR seems like an interesting choice. attracted my attention one day. I would also ...

11

If you can compute products with $A$ and $A^T$, as you specify in a comment, you can run the classical sparse SVD algorithms such as scipy.sparse.linalg.svds, Matlab's svds, or Julia's Arpack.svds, which are based on Lanczos bidiagonalization. They are designed to compute singular values, and are likely to be more robust than a minimization routine coded by ...

1

Here's my 2 cents. I would set up the following minimization problem $$\pi(x) = \frac{1}{2} (Ax)^T(Ax)$$ If $A$ has eigenvalues which are zero, there will exist a nonzero $x$ such that $\pi(x)=0$. So, I would try computing the gradient of $\pi$ wrt $x$ and use a gradient descent algorithm to drive $\pi$ towards zero. If you get reasonably close to zero (\$\...

3

LAPACK has an implementation of the svd of a 2x2 triangular matrix. It appears to be very robust. The routine is XLASV2. To apply to a regular 2x2 matrix, you can simply apply a single givens rotation from the left/right.

0

Briefly, referencing the Julia documentation on linear algebra subroutines, they note that the Bunch-Kaufman factorization method is more appropriate for symmetric matrices.(old source from NASA) It may go without saying that positive definite matrices are a subset of symmetric matrices, so while Bunch-Kaufman factorization is an improvement, it isn't ...

0

You can and should solve this problem without linear programming and apply the Bellman equation instead. Actually, the minmax theorem -- handled numerically via LP -- is only required to solve the problem where both players simultaneously choose an action. In contrast, your game consists of a two-step process, and the mathematical model should incorporate ...

Top 50 recent answers are included