Linear algebra over a polynomial ring

[Nahuel Freitas]

Hello everyone,

I am a physics student and I need to do the following as part of my research: I have a matrix A whose elements are uni-variate polynomials over the rationals, and I need to compute the determinant and adjoint matrix of A. I known I can do it with SAGE, PARI or SINGULAR, but efficiency is a concern so I am looking for a pure c++ solution, since I don't want to communicate to another piece of software. I was playing around with Linbox but I couldn't instantiate matrices over polynomials rings. Today I found LELA and it would be very useful to me if someone here can tell me if the library is of any help to do what I need. 

The tutorial says that only the following rings are built-in in LELA:

• Integers, for integers (actually a wrapper for GMP)
• Rationals, for rational numbers (also a wrapper for GMP)
• Modular, for integers modulo n,
• GF2 (for fast computations over GF(2)), and
• TypeWrapperRing (a wrapper around any type which implements the basic arithmetic-operations +, -, *, /, and %)

So it seems that LELA doesn't implement polynomial rings, but maybe is not so hard to implement it, maybe using TypeWrapperRing. Any guide about this will be useful.

Thanks in advance.

Nahuel Freitas.

[Bradford Hovinen]

Hello Nahuel,

Your assumption that LELA does not currently implement polynomial rings is correct. It should however be no problem to implement one. If you already have a class available which provides objects which override the standard arithmetic operations, then TypeWrapperRing will do the trick. Otherwise you will have to write a class which delivers the required interface as given in lela/rings/interface.h

The perhaps larger problem is that LELA does not currebtly implement any algorithms for PIDs such as univariate polynomial rings. The main application thus far has been computing the row-echelon forms of matrices over GF(2), and we haven't had the resources to focus on other areas yet. All basic matrix-arithmetic is however available, and one could in principle build an algorithm to do what you want using the tools which LELA provides, but the performance might not be so great, since operations with complex objects are not so well optimised. The focus is instead to optimise arithmetic of matrices over really "simple" rings, such as finite fields.

Nevertheless that can help you. One relatively simple approach which would let you take advantage of the best low level techniques is:
1. Pick a suitably large set of primes not dividing any of the denominators of the matrix.
2. Reduce the matrix modulo each of the primes.
3. For each chosen prime p, pick a suitably large set of integers between 0 and p-1 at which to evaluate the polynomials therein and evaluate the matrix at those points.
4. Compute the determinant resp. the adjoint of each reduced matrix in the respective field.
5. Use polynomial interpolation and rational reconstruction to recover the desired result.

You can use LELA for the fourth step above. There are also some facilities to help with some of the other steps (such as a pseudorandom number generator).

I would have to look up the data on how many primes and evaluation-points you would need (I am unfortunately travelling at the moment and have limited access to such things). For best performance, use a floating point representation for the reduced and evaluated matrix and pick suitably sized primes. Then the calculations are done with BLAS, which should be quite efficient.

If you have further questions, please don't hesitate to ask.

Best regards,

Bradford Hovinen

> --
> You received this message because you are subscribed to the Google Groups "LELA Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to lela-users+...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>  
>  
>

[Nahuel Freitas]

Bradford,

Thank you very much for your answer and time! I will consider your suggestions!

Cheers,

Nahuel.