Optimize nassau::Resolution::write_qi

[JoeyBF]

Right now this line

sseq/ext/src/nassau.rs

Line 519 in 127aa0f

scratch.as_slice_mut().add(full_matrix.row(i), 1);

is extremely hot. I would even say it's one of the main bottlenecks to computing at large stems. Looking at active threads with top and running pstack on them periodically, it seems I usually have only a handful of threads running, and they are all executing that line. (See #101 for more detailed logging)

If I'm reading this correctly, this code looks like it's doing some vector-vector operations repeatedly. Would this be a good candidate to replace with vector-matrix or matrix-matrix operations? In the latter case #100 will probably give a massive speedup.

[dalcde]

This is essentially computing the quasi-inverse, which is doing some necessary work. There is probably still room for improvement though. I would suspect this is more memory-bound than CPU-bound; I don't thing we are reading things in a very cache-friendly way.

[JoeyBF]

I still think this is one of the biggest improvements we could make right now, even more than computing Milnor products faster. Here's a snippet from the logs

[   134.430488 s] [    4.003 MiB/s] Written quasi-inverse for bidegree (233, 17) and signature [5, 0, 1], with A(2)
[    22.426958 s] [   11.430 MiB/s] Written quasi-inverse for bidegree (249, 12) and signature [2, 7, 1, 0], with Algebra with profile [3, 3, 2, 1]
[    11.016714 s] [   17.820 MiB/s] Written quasi-inverse for bidegree (252, 11) and signature [7, 0, 0, 1], with A(3)
[   250.689435 s] [    3.119 MiB/s] Written quasi-inverse for bidegree (245, 13) and signature [6, 1, 1, 0], with Algebra with profile [3, 2, 1, 1]
[    10.547717 s] [   18.874 MiB/s] Written quasi-inverse for bidegree (252, 11) and signature [8, 0, 0, 1], with A(3)
[   522.460866 s] [    2.211 MiB/s] Written quasi-inverse for bidegree (239, 14) and signature [7, 0, 0], with A(2)
[    23.604541 s] [   11.215 MiB/s] Written quasi-inverse for bidegree (249, 12) and signature [3, 7, 1, 0], with Algebra with profile [3, 3, 2, 1]
[     9.622013 s] [   19.545 MiB/s] Written quasi-inverse for bidegree (252, 11) and signature [9, 0, 0, 1], with A(3)
[   210.080566 s] [    3.112 MiB/s] Written quasi-inverse for bidegree (236, 15) and signature [5, 3, 1], with A(2)

I still feel like we could make use of matrix-matrix operations but I don't understand the code well enough yet