Opened 8 years ago

Closed 8 years ago

# faster matrix integer dense

Reported by: Owned by: vdelecroix major sage-6.6 linear algebra Vincent Delecroix Jeroen Demeyer N/A d48c188 d48c188400d02ee7df99820b30fd8dc6a8f1bfc9

We now have a flint implementation of dense integer matrices. The branch proposes various optimization in `matrix.matrix_integer_dense` to make it faster.

### comment:1 Changed 8 years ago by vdelecroix

Branch: → u/vdelecroix/17822 → f7e649670dc0ec095b45471a4b8a39e2773a24c5 new → needs_review

New commits:

 ​f7e6496 `trac #17822: faster Matrix_integer_dense`

### comment:2 Changed 8 years ago by vdelecroix

new timings:

```sage: M = MatrixSpace(ZZ,3)
sage: m = M([1,2,3,4,5,6,1,2,-3])
sage: %timeit m*m
1000000 loops, best of 3: 1.13 µs per loop
sage: %timeit m**3
100000 loops, best of 3: 2.04 µs per loop
sage: %timeit m**100
100000 loops, best of 3: 7.71 µs per loop
sage: %timeit m**-100
1000 loops, best of 3: 377 µs per loop
sage: %timeit ~m
10000 loops, best of 3: 37 µs per loop
sage: M1 = MatrixSpace(ZZ,4,2)
sage: m1 = M1(range(8))
sage: M2 = MatrixSpace(ZZ,3,4)
sage: m2 = M2(range(12))
sage: %timeit m2*m1
100000 loops, best of 3: 4.8 µs per loop
```

same operations on sage-6.6.beta0:

```sage: M = MatrixSpace(ZZ,3)
sage: m = M([1,2,3,4,5,6,1,2,-3])
sage: %timeit m*m
100000 loops, best of 3: 4.72 µs per loop
sage: %timeit m**3
100000 loops, best of 3: 10.2 µs per loop
sage: %timeit m**100
10000 loops, best of 3: 45.8 µs per loop
sage: %timeit m**-100
1000 loops, best of 3: 462 µs per loop
sage: %timeit ~m
1000 loops, best of 3: 138 µs per loop
sage: M1 = MatrixSpace(ZZ,4,2)
sage: m1 = M1(range(8))
sage: M2 = MatrixSpace(ZZ,3,4)
sage: m2 = M2(range(12))
sage: %timeit m2*m1
100000 loops, best of 3: 10.7 µs per loop
```
Last edited 8 years ago by vdelecroix (previous) (diff)

### comment:3 Changed 8 years ago by jdemeyer

Instead of `mpz_cmp_ui((<Integer>n).value, ULONG_MAX) < 1:`, why not use `mpz_fits_ui` which is exactly made for that purpose?

### comment:4 Changed 8 years ago by git

Commit: f7e649670dc0ec095b45471a4b8a39e2773a24c5 → f796fa883dea2e337450f3cb7a0edeb78a692655

Branch pushed to git repo; I updated commit sha1. New commits:

 ​f796fa8 `trac #17822: use mpz_fits_ulong_p`

### comment:5 Changed 8 years ago by git

Commit: f796fa883dea2e337450f3cb7a0edeb78a692655 → 1cb707b613aa01dce6c4c4a50770ace3aec65345

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​1cb707b `trac #17822: use mpz_fits_ulong_p`

### comment:6 Changed 8 years ago by git

Commit: 1cb707b613aa01dce6c4c4a50770ace3aec65345 → 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d

Branch pushed to git repo; I updated commit sha1. New commits:

 ​555bcd2 `trac #17822: TypeError -> ArithmeticError in _inverse_flint`

### comment:7 Changed 8 years ago by vdelecroix

Description: modified (diff)

### comment:8 Changed 8 years ago by git

Commit: 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d → bb38f4b52d27e56907c19538052c871e0a03a632

Branch pushed to git repo; I updated commit sha1. New commits:

 ​bb38f4b `trac #17822: remove duplicated __copy__`

### comment:9 Changed 8 years ago by jdemeyer

Why did you move `__copy__`? It's harder to review that way.

```cdef object P
```

since it serves no purpose.

### comment:10 Changed 8 years ago by git

Commit: bb38f4b52d27e56907c19538052c871e0a03a632 → 09575df74d198c8f0dba694dcfe94687ebe42afb

Branch pushed to git repo; I updated commit sha1. New commits:

 ​09575df `trac #17822: remove useless declaration`

### comment:11 follow-up:  12 Changed 8 years ago by vdelecroix

Why did you move `__copy__`? It's harder to review that way.

`__copy__` is referenced in the list of LEVEL 2 functionalities. So I first implement it there and then I discover that it was already in the begining of the file.

```cdef object P
```

since it serves no purpose.

right.

### comment:12 in reply to:  11 ; follow-up:  13 Changed 8 years ago by jdemeyer

`__copy__` is referenced in the list of LEVEL 2 functionalities.

What does this "LEVEL 2 functionalities" mean anyway?

### comment:13 in reply to:  12 Changed 8 years ago by vdelecroix

`__copy__` is referenced in the list of LEVEL 2 functionalities.

What does this "LEVEL 2 functionalities" mean anyway?

It refers to the crazy organization of the matrix code inside `matrix0.pyx`, `matrix1.pyx` and `matrix2.pyx`.

### comment:14 Changed 8 years ago by jdemeyer

Branch: u/vdelecroix/17822 → u/jdemeyer/ticket/17822 Feb 21, 2015, 4:17:00 PM → Feb 21, 2015, 4:17:00 PM Feb 23, 2015, 2:22:35 PM → Feb 23, 2015, 2:22:35 PM

### comment:15 Changed 8 years ago by jdemeyer

Commit: 09575df74d198c8f0dba694dcfe94687ebe42afb → d48c188400d02ee7df99820b30fd8dc6a8f1bfc9 → Jeroen Demeyer

Reviewer patch needs review.

New commits:

 ​d48c188 `Reviewer patch`

### comment:16 follow-up:  18 Changed 8 years ago by vdelecroix

What is this Cython syntax for?

```cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself
```

### comment:17 follow-up:  19 Changed 8 years ago by jdemeyer

It's a cast with check. In particular, it disallows `sself = None`.

Last edited 8 years ago by jdemeyer (previous) (diff)

### comment:18 in reply to:  16 Changed 8 years ago by vdelecroix

What is this Cython syntax for?

```cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself
```

just found out "cast type checked".

### comment:19 in reply to:  17 Changed 8 years ago by vdelecroix

It's a cast with check. In particular, it disallows `sself = None`.

`sself` can be `None` here!?

Last edited 8 years ago by vdelecroix (previous) (diff)

### comment:20 Changed 8 years ago by jdemeyer

If you do `None^M` with `M` an integer matrix, then yes.

### comment:21 follow-up:  22 Changed 8 years ago by vdelecroix

Status: needs_review → positive_review

Thanks for the improvements! (And if you have time, there is the follow up #17824)