2
$\begingroup$

A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use Cholesky decomposition which is more efficient than LU decomposition. If the entries of $A$ are all integers one can use the Bareiss algorithm which is similar to Gaussian elimination but only does divisions that are exact for integers thus avoiding fractions.

My question is: Is there a version of Bareiss algorithm or some other similar algorithm for symmetric integer matrices such that it would utilize the symmetry and use less operations than the basic Bareiss algorithm?

$\endgroup$
4
  • $\begingroup$ Please do not post the same question on multiple sites. I suggest that you pick one site where you think this best fits. Which site would you like this to appear on? $\endgroup$
    – D.W.
    Jun 28, 2023 at 5:58
  • $\begingroup$ @D.W. Which site would be the best site for this question? What do I do if the site I chose turns out not to be the best site? Should I then delete it and post it on another site? $\endgroup$
    – QuantumWiz
    Jun 28, 2023 at 7:41
  • $\begingroup$ My guess is that this site is the best choice, since you are asking for algorithms. Yes, if you later discover you asked on the wrong site, deleting on the original one and asking elsewhere seems reasonable (do try to address any feedback you got). $\endgroup$
    – D.W.
    Jun 28, 2023 at 17:05
  • $\begingroup$ OK, I deleted the question about this on Mathematics Stack Exchange. $\endgroup$
    – QuantumWiz
    Jul 7, 2023 at 21:06

1 Answer 1

0
$\begingroup$

Standard Cholesky requires square roots, which will break the integral property. The method you are after is probably LDL decomposition. https://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition

$\endgroup$
6
  • $\begingroup$ But you also need to make sure that only exact divisions with integer results can occur. At least in basic Gaussian elimination (and LU decomposition) the divisions will often result in fractions even with integer matrices which is why Bareiss's modification is necessary to avoid fractions. Similarly, the basic LDL decomposition can result in fractions (take e.g. a 2x2 matrix with 2 on both diagonal entries and 1 on the off-diagonals). Maybe fractions can be avoided by using a modification similar to Bareiss but I don't know how to do that in the case of LDL. $\endgroup$
    – QuantumWiz
    Jun 29, 2023 at 21:45
  • $\begingroup$ @QuantumWiz: elimination can always be performed without divisions. By Cramer's rule, every solution can be written as D Xi = Di, where the D are integer determinants. $\endgroup$
    – user16034
    Jun 30, 2023 at 6:18
  • $\begingroup$ If no divisions are used the integers can grow in size a lot. The point of Bareiss algorithm is that it performs certain kind of divisions where it's always guaranteed that the divisor divides the dividend exactly. This limits how much the integers grow but still avoids producing fractions. $\endgroup$
    – QuantumWiz
    Jun 30, 2023 at 7:30
  • $\begingroup$ @QuantumWiz: anyway, simplification can be used (division by the gcd of the coefficients). If the coefficients can remain small integers, they will. But of course, one must investigate if the Bareiss trick remains possible (though it can produce huge integers as well). $\endgroup$
    – user16034
    Jun 30, 2023 at 8:00
  • $\begingroup$ GCD can be a relatively expensive calculation. I'm curious whether that could be avoided while still performing some divisions like in the case of Bareiss. $\endgroup$
    – QuantumWiz
    Jun 30, 2023 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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