Multiple precision matrices
Décio Luiz Gazzoni Filho
decio at decpp.net
Wed May 25 15:33:25 UTC 2016
> 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).
More information about the gmp-discuss