Multiple precision matrices

[Décio Luiz Gazzoni Filho]

> On May 25, 2016, at 10:08 AM, Torbjörn Granlund <tg at gmplib.org> wrote:
> 
> Kartik Gupta <kartik.kailash.gupta at gmail.com> writes:
> 
>  Does GMP provide the functionality of doing fast multiple precision matrix
>  operations like addition, multiplication, etc?
>  Or is there any other library available which builds upon GMP or otherwise
>  provides these functionalities?
>  I am building a system where I will be using matrices of multiple precision
>  integers and performing some computations on them.
> 
> We might want to support that at some point, as the benefits of doing it
> at a low level are great.  If one uses that plain O(mnk) algorithm (for
> multiplying an m,n and an n,k matrix) one currently will perform 3mnk
> FFT transforms.  If we implement this with access to the FFT types, one
> could reduce this to mn + nk + mk FFT transforms.
> 
> (Depending on which ring we use for the polynomial coefficients in FFT,
> this may not only save most of the work in practice, but also reduce the
> time complexity.  This is not true for the current GMP FFT, but is true
> for the small primes FFT which we have in the works.)

Not to mention the use of Strassen’s algorithm which might reduce the cost to O(n^2.807) for square matrices of dimension n, or if you really want to go all the way, the Coppersmith-Winograd algorithm with cost O(n^2.38).

Décio