Opened 9 months ago

Closed 5 months ago

#28245 closed enhancement (fixed)

Implement center of a HyperplaneArrangement

Reported by: nailuj Owned by:
Priority: minor Milestone: sage-9.0
Component: geometry Keywords: HyperplaneArrangements, days100
Cc: jipilab Merged in:
Authors: Julian Ritter Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: b74518a (Commits) Commit: b74518afc8c4b987177aca618280627ebfb87162
Dependencies: Stopgaps:

Description

This ticket implements the following changes to the class HyperplaneArrangementElement:

  • In the method is_central, add the argument certificate=False. If set to True, this will additionally return the center of the arrangement. The center is easily obtainable as a byproduct of the existing calculation.
  • Add the method center(). This will return the center of the arrangement as computed by is_central(certificate=True).

Change History (28)

comment:1 Changed 9 months ago by nailuj

  • Branch set to u/nailuj/implement_center_of_a_hyperplanearrangement

comment:2 Changed 9 months ago by git

  • Commit set to d8b282c628c8f890130feb1a84c7143d59a16a82

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

d8b282cupdated docstring of is_central

comment:3 follow-up: Changed 9 months ago by jipilab

Here are few schönheitssachen:

  • space after comma in the definition (pep8 conventions...)
  • swap (default: False) and boolean in the docstring
  • I would use the verb return instead of include
  • is_central needs the appropriate doctests checking all possibilities.
  • center needs an example when the hyperplane arrangement is not central.

I would suggest to use the Polyhedra parents and then return .universe() and .empty() which are less costly to execute in principle.

comment:4 Changed 8 months ago by git

  • Commit changed from d8b282c628c8f890130feb1a84c7143d59a16a82 to d72e65e7b308a61f680004cd8078ec6cf65dd014

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

57948dacleaned up docstring of is_central
5f16740commented doctests for center method
67a4ff7use Polyhedra parents for universe and empty
d72e65eadd doctest for is_central

comment:5 in reply to: ↑ 3 Changed 8 months ago by nailuj

  • Authors set to Julian Ritter
  • Status changed from new to needs_review

Replying to jipilab:

Here are few schönheitssachen:

  • space after comma in the definition (pep8 conventions...)

Done.

  • swap (default: False) and boolean in the docstring

Done.

  • I would use the verb return instead of include

Done.

  • is_central needs the appropriate doctests checking all possibilities.

Done.

  • center needs an example when the hyperplane arrangement is not central.

Done.

I would suggest to use the Polyhedra parents and then return .universe() and .empty() which are less costly to execute in principle.

Done.

comment:6 follow-up: Changed 8 months ago by jipilab

  • Status changed from needs_review to needs_work

No need of a bullet list for one element:

-        If ``certificate`` is False:
-
-        - A boolean
+        If ``certificate`` is ``False``, returns a boolean
  • Missing empty lines before the doctests (in both functions).
  • I would shorten the output of center to simply say that it is a polyhedron. If you want to be explicit, I would do it in the longer description before input/output.

comment:7 Changed 8 months ago by git

  • Commit changed from d72e65e7b308a61f680004cd8078ec6cf65dd014 to 80b98c485aa1474f6b9729c9319123de0eb58d19

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

80b98c4cosmetic changes

comment:8 in reply to: ↑ 6 Changed 8 months ago by nailuj

  • Status changed from needs_work to needs_review

Replying to jipilab:

No need of a bullet list for one element:

-        If ``certificate`` is False:
-
-        - A boolean
+        If ``certificate`` is ``False``, returns a boolean

Rephrased.

  • Missing empty lines before the doctests (in both functions).

Inserted.

  • I would shorten the output of center to simply say that it is a polyhedron. If you want to be explicit, I would do it in the longer description before input/output.

Moved.

comment:9 follow-up: Changed 8 months ago by jipilab

I noted another small thing:

+        If ``certificate`` is True, returns a tuple containing:
+
+        1. A boolean
+        2. The polyhedron defined to be the intersection of all the hyperplanes
+
+        If ``certificate`` is False, returns a boolean.

True and False should be between two back ticks... Otherwise, looks good. Just waiting that bots go over it again...

comment:10 Changed 8 months ago by jipilab

  • Status changed from needs_review to needs_work

comment:11 Changed 8 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé

comment:12 Changed 8 months ago by git

  • Commit changed from 80b98c485aa1474f6b9729c9319123de0eb58d19 to c0b2f38a6c8231179a1fde55288e10fc51711350

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

c0b2f38backticks for True and False

comment:13 in reply to: ↑ 9 Changed 8 months ago by nailuj

  • Status changed from needs_work to needs_review

Replying to jipilab:

I noted another small thing:

+        If ``certificate`` is True, returns a tuple containing:
+
+        1. A boolean
+        2. The polyhedron defined to be the intersection of all the hyperplanes
+
+        If ``certificate`` is False, returns a boolean.

True and False should be between two back ticks...

Done.

comment:14 follow-up: Changed 8 months ago by tscrim

A little doc change:

         - ``certificate`` -- boolean (default: ``False``); specifies whether
-        to return the center as a polyhedron (possibly empty) as part of the 
-        output.
           to return the center as a polyhedron (possibly empty) as part
           of the output

(Note also the lack of a period/full-stop and the removal of the trailing whitespace.)

Also, because of the @cached_method, there is no reason to do the computation twice. Constructing the certificate seems quite cheap to me, so I might instead put as the first lines:

if not certificate:
    return self.is_central(True)[0]

and then assume certificate=True for the rest. However, this really depends on how expensive that right_kernel is and how often you think the certificate will be requested. There is a balance to be had here and a judgement call to be made. I am just saying this is an alternative way to avoid doing the main computation twice should you ask for with a certificate and without.

comment:15 Changed 8 months ago by chapoton

doc does not build

HyperplaneArrangementElement.is_central:9:
WARNING: Bullet list ends without a blank line; unexpected unindent.

comment:16 Changed 7 months ago by chapoton

  • Status changed from needs_review to needs_work

comment:17 Changed 7 months ago by git

  • Commit changed from c0b2f38a6c8231179a1fde55288e10fc51711350 to b74518afc8c4b987177aca618280627ebfb87162

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

b74518acorrected indentation in documentation

comment:18 in reply to: ↑ 14 ; follow-up: Changed 7 months ago by nailuj

  • Status changed from needs_work to needs_review

Replying to tscrim:

A little doc change:

         - ``certificate`` -- boolean (default: ``False``); specifies whether
-        to return the center as a polyhedron (possibly empty) as part of the 
-        output.
           to return the center as a polyhedron (possibly empty) as part
           of the output

(Note also the lack of a period/full-stop and the removal of the trailing whitespace.)

Thanks, I was not careful enough with these conventions.

Also, because of the @cached_method, there is no reason to do the computation twice. Constructing the certificate seems quite cheap to me, so I might instead put as the first lines:

if not certificate:
    return self.is_central(True)[0]

and then assume certificate=True for the rest. However, this really depends on how expensive that right_kernel is and how often you think the certificate will be requested. There is a balance to be had here and a judgement call to be made. I am just saying this is an alternative way to avoid doing the main computation twice should you ask for with a certificate and without.

Thank you for sharing these thoughts. If both methods had been new, I probably would have done the right_kernel calculation and just decided to return it or not depending on the certificate switch. But as is_central was already implemented, I considered not slowing down the existing method more important than obtaining a faster computation of the new method center. Is this a good approach to deciding such issues?

comment:19 in reply to: ↑ 18 ; follow-up: Changed 7 months ago by jipilab

Replying to nailuj:

Replying to tscrim:

A little doc change:

         - ``certificate`` -- boolean (default: ``False``); specifies whether
-        to return the center as a polyhedron (possibly empty) as part of the 
-        output.
           to return the center as a polyhedron (possibly empty) as part
           of the output

(Note also the lack of a period/full-stop and the removal of the trailing whitespace.)

Thanks, I was not careful enough with these conventions.

Also, because of the @cached_method, there is no reason to do the computation twice. Constructing the certificate seems quite cheap to me, so I might instead put as the first lines:

if not certificate:
    return self.is_central(True)[0]

and then assume certificate=True for the rest. However, this really depends on how expensive that right_kernel is and how often you think the certificate will be requested. There is a balance to be had here and a judgement call to be made. I am just saying this is an alternative way to avoid doing the main computation twice should you ask for with a certificate and without.

Thank you for sharing these thoughts. If both methods had been new, I probably would have done the right_kernel calculation and just decided to return it or not depending on the certificate switch. But as is_central was already implemented, I considered not slowing down the existing method more important than obtaining a faster computation of the new method center. Is this a good approach to deciding such issues?

It sounds reasonable, yes. Though I actually like Travis's idea of not having to recompute the function, however it was called first. Is it hard to switch to this?

comment:20 in reply to: ↑ 19 ; follow-up: Changed 7 months ago by nailuj

Replying to jipilab:

Replying to nailuj:

Replying to tscrim:

Also, because of the @cached_method, there is no reason to do the computation twice. Constructing the certificate seems quite cheap to me, so I might instead put as the first lines:

if not certificate:
    return self.is_central(True)[0]

and then assume certificate=True for the rest. However, this really depends on how expensive that right_kernel is and how often you think the certificate will be requested. There is a balance to be had here and a judgement call to be made. I am just saying this is an alternative way to avoid doing the main computation twice should you ask for with a certificate and without.

Thank you for sharing these thoughts. If both methods had been new, I probably would have done the right_kernel calculation and just decided to return it or not depending on the certificate switch. But as is_central was already implemented, I considered not slowing down the existing method more important than obtaining a faster computation of the new method center. Is this a good approach to deciding such issues?

It sounds reasonable, yes. Though I actually like Travis's idea of not having to recompute the function, however it was called first. Is it hard to switch to this?

As Travis wrote, there are two lines to be inserted and some lines to be deleted, that would be all. If you think the additional computation time for the right_kernel and the construction of the Polyhedron aren't slowing down is_central too much, I could do it.

comment:21 in reply to: ↑ 20 Changed 7 months ago by jipilab

Replying to nailuj:

Replying to jipilab:

Replying to nailuj:

Replying to tscrim:

Also, because of the @cached_method, there is no reason to do the computation twice. Constructing the certificate seems quite cheap to me, so I might instead put as the first lines:

if not certificate:
    return self.is_central(True)[0]

and then assume certificate=True for the rest. However, this really depends on how expensive that right_kernel is and how often you think the certificate will be requested. There is a balance to be had here and a judgement call to be made. I am just saying this is an alternative way to avoid doing the main computation twice should you ask for with a certificate and without.

Thank you for sharing these thoughts. If both methods had been new, I probably would have done the right_kernel calculation and just decided to return it or not depending on the certificate switch. But as is_central was already implemented, I considered not slowing down the existing method more important than obtaining a faster computation of the new method center. Is this a good approach to deciding such issues?

It sounds reasonable, yes. Though I actually like Travis's idea of not having to recompute the function, however it was called first. Is it hard to switch to this?

As Travis wrote, there are two lines to be inserted and some lines to be deleted, that would be all. If you think the additional computation time for the right_kernel and the construction of the Polyhedron aren't slowing down is_central too much, I could do it.

I would say it is fine yes.

Unless you find an example where you have tons of hyperplanes (10 000+) I don't think it will take too much time. Just for the record, if speed is really important, you could benchmark the before and after for some relatively big example just to have an idea...

comment:22 follow-up: Changed 5 months ago by jipilab

  • Status changed from needs_review to needs_info

Hi Julian,

Are you going to do the suggested changes? It looks ok to me either way.

J-P

comment:23 in reply to: ↑ 22 Changed 5 months ago by nailuj

Replying to jipilab:

Hi Julian,

Are you going to do the suggested changes? It looks ok to me either way.

J-P

Hi, I forgot about implementing the suggested changes. If you ask me like that, I would prefer the way it is written right now.

comment:24 Changed 5 months ago by jipilab

  • Status changed from needs_info to needs_review

Ok, sounds good.

I'm setting it to "needs review" to get another round of bots testing it, just for sanity reasons.

comment:25 Changed 5 months ago by tscrim

(Morally) Green patchbots.

comment:26 Changed 5 months ago by jipilab

  • Status changed from needs_review to positive_review

Ok, may it be.

comment:27 Changed 5 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

comment:28 Changed 5 months ago by vbraun

  • Branch changed from u/nailuj/implement_center_of_a_hyperplanearrangement to b74518afc8c4b987177aca618280627ebfb87162
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.