1
$\begingroup$

In quantum mechanics, the wavefunction of N electrons is given by a determinant. I am working on a Monte Carlo algorithm. At each Monte Carlo step, I need to add or remove an electron, which means adding or removing a line and a column to my matrix.

I use Gauss elimination to compute an upper triangle matrix. Adding a line and a column is simple and can be done in a time growing as $O(n^2)$. Removing the last line and column is also feasible simply in $O(n^2)$. To the ith line, I saw no other possibilty than recomputing the pivots from i to n-1 which requires a time $O(n^3)$.

Does anybody see another possibily?

$\endgroup$
3
$\begingroup$

If changes in pivoting are an issue, then yes, to my knowledge there is no obvious $O(n^3)$ solution. However, you could consider switching to the QR factorization. That factorization costs twice as much as LU for the initial computation, but it can be updated in a stable way in $O(n^2)$. See Golub and Van Loan Matrix Computations for algorithms, or https://www.mathworks.com/help/matlab/ref/qrupdate.html and https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.qr_update.html for implementations. The code unfortunately is not in Lapack.

If your matrix happens to be symmetric positive definite, then there are also methods to update its Cholesky factorization for much cheaper, preserving symmetry.

Both factorizations reveal at least $|\det A|$. It may be tricky to keep track of the sign of $\det(Q)$, if you need it, but it should be determined uniquely because each QR does just a number of Householder ($\det=-1$) or Givens ($\det=1$) updates.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Thank you! The algorithm is also implemented in GNU/Octave. There are functions to insert (qrinsert) or remove (qrdelete) a column or a row. Precisely what I need! $\endgroup$ – Christophe Jan 17 at 16:05

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.