#29906 closed enhancement (fixed)

Run tests for `an_affine_basis`

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: polyhedra, test suite
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: f57e162 (Commits, GitHub, GitLab) Commit: f57e162f65b6f29c80a9e6d079cd3378cb122b85
Dependencies: #29903 Stopgaps:

Status badges

Description

This ticket adds a method that tests an_affine_basis to Polyhedron_base.

We move some basic tests there.

Change History (8)

comment:1 Changed 13 months ago by git

  • Commit changed from 5d79b2ba522c2f44aba5f5acbf3e5336b0b5f987 to af2ba1f27e0bcfd1e46b4de0787d0b283c46cbac

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

af2ba1ftest suite for an_affine_basis

comment:2 Changed 13 months ago by git

  • Commit changed from af2ba1f27e0bcfd1e46b4de0787d0b283c46cbac to 5d79b2ba522c2f44aba5f5acbf3e5336b0b5f987

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

comment:3 Changed 13 months ago by gh-kliem

  • Branch changed from public/29903 to public/29906
  • Commit changed from 5d79b2ba522c2f44aba5f5acbf3e5336b0b5f987 to af2ba1f27e0bcfd1e46b4de0787d0b283c46cbac
  • Dependencies set to #29903
  • Status changed from new to needs_review

New commits:

af2ba1ftest suite for an_affine_basis

comment:4 Changed 13 months ago by tscrim

Is there some way to improve this test:

m = matrix(b).transpose().stack(matrix([[1]*len(b)]))

It feels somewhat inefficient as you make a matrix then take its transpose. Plus you get a new matrix with the stack call. Wouldn't it be better to just add 1 to each of the vectors b then ask for the rank?

comment:5 Changed 13 months ago by gh-kliem

It does feel inefficient, but I think it is rather efficient (besides that it really doesn't matter as obtaining an_affine_matrix takes much longer than anything else here):

sage: P = polytopes.permutahedron(7)

sage: 
sage: b = P.vertices()
sage: len(b)
5040
sage: P = polytopes.permutahedron(7)
sage: b = P.vertices()
sage: len(b)
5040
sage: def hom_matrix1(b):
....:     return matrix(b).transpose().stack(matrix([[1]*len(b)]))
....: 
sage: def hom_matrix2(b):
....:     return matrix([1] + list(x) for x in b)
....: 
sage: def hom_matrix3(b):
....:     return matrix(b).transpose().stack(vector([1]*len(b)))
....: 
....: 
sage: %timeit hom_matrix1(b)
10 loops, best of 5: 19.6 ms per loop
sage: %timeit hom_matrix2(b)
10 loops, best of 5: 23.4 ms per loop
sage: %timeit hom_matrix3(b)
10 loops, best of 5: 26 ms per loop

sage: b = P.an_affine_basis()
sage: len(b)
sage: %timeit hom_matrix1(b)
The slowest run took 98.27 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 46.1 µs per loop
sage: %timeit hom_matrix2(b)
The slowest run took 12.89 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 35.1 µs per loop
sage: %timeit hom_matrix3(b)
The slowest run took 4.52 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 103 µs per loop

So it is a bit faster for small instances (which should always be true for b being an affine basis of any TestSuite polyhedron, but really not by much. Besides it is a meaningless time difference if you consider obtaining an_affine_basis first, even with #29841.

If you know argue that matrix([1] + list(x) for x in b) is much easier to understand, I agree with you and that is a good point.

comment:6 Changed 13 months ago by git

  • Commit changed from af2ba1f27e0bcfd1e46b4de0787d0b283c46cbac to f57e162f65b6f29c80a9e6d079cd3378cb122b85

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

f57e162more transparent test for an_affine_basis

comment:7 Changed 13 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Likely in the small cases you're seeing the benefit from everything being done in Cython rather than Python. I am not sure if I would say it is easier to understand. The transpose and stacking makes it more clear how things should be grouped, but it is not as clear that things are being realized as embedding in an affine space in a vector space. However, there are less moving parts, so I think that is a bonus with changing it. Plus it is better on the memory side if someone is working with a large polytope and wants to run this test.

Thank you for making the change.

comment:8 Changed 13 months ago by vbraun

  • Branch changed from public/29906 to f57e162f65b6f29c80a9e6d079cd3378cb122b85
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.