2
$\begingroup$

In a current research project, I have a number of matrices with coefficients in ℚ[𝑥] for which I want to understand how their rank depends on the value of the parameter 𝑥.

These matrices are:

  • sparse (a typical example is a matrix of size 160x200 with less than 10 non-zero entries per row),
  • rather 'regular' (each entry is a polynomial of degree at most one), and relatively
  • close to full rank (in the above example of 160x200 rank is at least 150 no matter what the parameter is).

I would like to find software that can try to speed up calculations knowing at least some of these special features. So far I mostly tried Magma, and the calculations get endlessly long very fast for the sizes of matrices that I need. (I would also appreciate advice on Magma since perhaps I am forgetting some options that one should specify, I just tried the default versions of HermiteForm and ElementaryDivisors).

Improve this question
$\endgroup$
4
  • $\begingroup$ How do you imagine these special properties can be used? For example I think the fact that the entries of the matrix are at most degree 1 is of only limited use because the entries of the HNF can still be of much higher degree. $\endgroup$
    – Daniel Shapero
    Oct 19, 2022 at 15:17
  • $\begingroup$ @DanielShapero I honestly am not sure (though presumably we all agree that sparsity is likely to be useful since it often helps optimizing algorithms). The condition on degree 1 for entries means that the matrix is of the form $A+xB$, and perhaps some methods used for fast computations of characteristic polynomials etc. can be naturally generalized? (Even though it is not a square matrix etc.) $\endgroup$
    – Vladimir Dotsenko
    Oct 19, 2022 at 15:27
  • 1
    $\begingroup$ Yea I suspect the sparsity is going to be the most important. I don't know what Magma does internally but it might be worth trying some kind of fill-reducing ordering of the matrix first. The elimination tree doesn't depend on the coefficient ring so in principle you have way more options in terms of software to play with there. $\endgroup$
    – Daniel Shapero
    Oct 19, 2022 at 15:51
  • $\begingroup$ @DanielShapero thanks! my intuition comes from other topics so "fill-reducing ordering" is already something new for me, I did a bit of reading and it sounds like a good thing to try. $\endgroup$
    – Vladimir Dotsenko
    Oct 19, 2022 at 17:47

0

Reset to default

Your Answer

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