0
$\begingroup$

Following up from this older question, I understand that calculation of determinants for integer-valued matrices is possible with polynomial scaling. However, I have been unable to locate any resources that describe computational complexities for matrices of floating-point numbers. I am particularly interested in the calculations of slater determinants using double precision, and would therefore like to ask the following question:

What is the lower (or upper) complexity bound for calculating the determinant of an $n$x$n$ matrix containing finite-precision floating-point numbers (e.g. single or double precision)? What about complex entries using floating point arithmetic?

$\endgroup$
3
  • $\begingroup$ Is your concern to improve on the cubic complexity of a QR decomposition, or minimizing floating-point errors, or using the sparsity structure, if present? Or something different? $\endgroup$
    – Lutz Lehmann
    Commented Nov 1, 2023 at 15:52
  • $\begingroup$ @LutzLehmann my understanding from the question I linked is that $O(n^3)$ scaling depends heavily on the nature of the entries within the matrix. As no information on floating-point numbers was given, I wanted to make sure whether this scaling holds for those types of entries as well. I wouldn't expect to be in a regime where floating-point errors become significant, but wanted to ensure specificity. Finally, I don't expect any sparsity structure to help me out immensely. $\endgroup$
    – KarimAED
    Commented Nov 1, 2023 at 16:47
  • $\begingroup$ $O(n^3)$ is the usual complexity for standard implementations of operations of matrices. It does not count the complexity of the number format. For instance integer determinants are best computed in modular arithmetic modulo a prime, combining results for different primes via the chinese remainder theorem. In other cases like the resultant, the determinant of the Sylvester matrix where the coefficients are themselves polynomials in a second variable, one needs to exploit the structure to avoid a too large explosion in the degree of the intermediate terms. $\endgroup$
    – Lutz Lehmann
    Commented Nov 1, 2023 at 17:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .