gap-packages / forms

Forms -- sesquilinear and quadratic, a package for GAP
https://gap-packages.github.io/forms
2 stars 3 forks source link

Make BaseChangeHermitian faster for large matrices #55

Closed fingolfin closed 8 months ago

fingolfin commented 8 months ago

... by performing row/column transformations directly instead of via matrix multiplication. This also reduces memory allocation and thus pressure on the garbage collector.

For comparison here are some timings using TestBaseChangeHermitian from tst/basechange.tst before and after this patch.

Before:

gap> TestBaseChangeHermitian(10, 7); [time,memory_allocated];
[ 1, 408841 ]
gap> TestBaseChangeHermitian(100, 7); [time,memory_allocated];
[ 736, 3232498670 ]
gap> TestBaseChangeHermitian(200, 7); [time,memory_allocated];
[ 8404, 51439492446 ]

After:

gap> TestBaseChangeHermitian(10, 7); [time,memory_allocated];
[ 2, 83971 ]
gap> TestBaseChangeHermitian(100, 7); [time,memory_allocated];
[ 78, 32690638 ]
gap> TestBaseChangeHermitian(200, 7); [time,memory_allocated];
[ 565, 244492918 ]

This is roughly on par with the orthogonal and symplectic cases:

gap> TestBaseChangeOrthogonalBilinear(10, 7); [time,memory_allocated];
[ 13, 1252868 ]
gap> TestBaseChangeOrthogonalBilinear(100, 7); [time,memory_allocated];
[ 96, 40882849 ]
gap> TestBaseChangeOrthogonalBilinear(200, 7); [time,memory_allocated];
[ 659, 305179561 ]

gap> TestBaseChangeSymplectic(10, 7); [time,memory_allocated];
[ 1, 50106 ]
gap> TestBaseChangeSymplectic(100, 7); [time,memory_allocated];
[ 49, 27109193 ]
gap> TestBaseChangeSymplectic(200, 7); [time,memory_allocated];
[ 212, 209951609 ]

Resolves #54 by @danielrademacher