Opened 4 years ago

Closed 4 years ago

#19258 closed defect (fixed)

Speedup tensor products of cyclotomic matrices

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-7.2
Component: number fields Keywords:
Cc: was, jdemeyer Merged in:
Authors: Travis Scrimshaw Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: a5e9fc0 (Commits) Commit: a5e9fc0fcb8386ba2cdd0e7beb1cdf441bcccd53
Dependencies: Stopgaps:

Description

Currently taking the tensor product of dense cyclotomic matrices takes forever: 

sage: R = CyclotomicField(2)
sage: M = matrix.random(R, 40,40)
sage: N = matrix.random(R, 3, 3)
sage: %time K = N.tensor_product(M)
CPU times: user 337 ms, sys: 20.6 ms, total: 358 ms
Wall time: 335 ms
sage: %time K = M.tensor_product(N)
CPU times: user 3.99 s, sys: 32.5 ms, total: 4.02 s
Wall time: 3.97 s

The tensor product code looses a lot of time in converting between its internal representation and the cyclotomic field entries. This ticket implements a custom tensor_product along with doing some other speedups with the internal workings.

Change History (5)

comment:1 Changed 4 years ago by tscrim

  • Branch set to public/matrices/speedup_cyclotomic_tensor_product-19258
  • Commit set to ff76bcd27b88e8b49f6001e40de36c9bd1ced32f
  • Status changed from new to needs_review

With the branch: 

sage: C = CyclotomicField(12)
sage: M = matrix.random(C, 3,3)
sage: N = matrix.random(C, 50, 50)
sage: %timeit M.tensor_product(N)
10 loops, best of 3: 88.8 ms per loop
sage: %timeit N.tensor_product(M)
1 loops, best of 3: 347 ms per loop

New commits:

​ff76bcdImplementing custom tensor_product for cyclotomic matrices.

comment:2 Changed 4 years ago by git

  • Commit changed from ff76bcd27b88e8b49f6001e40de36c9bd1ced32f to a5e9fc0fcb8386ba2cdd0e7beb1cdf441bcccd53

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

​a5e9fc0Removing unneeded import.

comment:3 Changed 4 years ago by tscrim

  • Cc jdemeyer added
  • Milestone changed from sage-6.9 to sage-6.11

comment:4 Changed 4 years ago by chapoton

  • Milestone changed from sage-7.0 to sage-7.2
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

comment:5 Changed 4 years ago by vbraun

  • Branch changed from public/matrices/speedup_cyclotomic_tensor_product-19258 to a5e9fc0fcb8386ba2cdd0e7beb1cdf441bcccd53
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.