Skip to content

Improve multiplication for ZZMatrix #1968

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
JohnAAbbott opened this issue Dec 6, 2024 · 1 comment
Open

Improve multiplication for ZZMatrix #1968

JohnAAbbott opened this issue Dec 6, 2024 · 1 comment

Comments

@JohnAAbbott
Copy link
Collaborator

Below is a "ridiculous" example: compute the square of a 1000x1000 identity matrix with the top right hand entry set to a large integer. The computation immediately grabs a lot of memory (about 40Gbyte on my computer), runs for a while, then is killed (presumably by systemd-oomd). The computation should be faster, and should not require so much RAM space.
Here is the OSCAR input to reproduce the problem -- it completes with sz = 500; or with exp = 5000

sz = 1000;
exp = 10000;
M = identity_matrix(ZZ,sz);
M[1,sz] = ZZ(10)^exp;
@time Msq = M^2;

This is much simplified from the original problematic computation -- a product of two upper triangular matrices with relatively few quite large entries.

@fredrik-johansson
Copy link
Contributor

This is a FLINT issue. fmpz_mat_mul chooses an algorithm based on the dimension and maximum height, but does not currently account for the distribution of heights.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants