Multiple precision matrices

Torbjörn Granlund tg at
Thu May 26 05:50:32 UTC 2016

Décio Luiz Gazzoni Filho <decio at> writes:

  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).
For bignum coefficients these "costs" might not give a good indication.

Neither our additions nor Our multiplies will be in O(1), so we have
three dimension variables (unless the matrices are square) and then a
ser of operand sizes.

At any rate, these faster algorithms tend to be more beneficial when
multiplication is comparatively slow as it is for bignum operations.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list