#19405: Add lyapunov_rank() method for polyhedral cones
-------------------------------------+-------------------------------------
Reporter: mjo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.10
Component: geometry | Resolution:
Keywords: | Merged in:
Authors: Michael Orlitzky | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/mjo/ticket/19405 | 0c1176c68504468baaeb754756c5808e49a5fcc5
Dependencies: #19368 | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Michael Orlitzky', 'oldvalue': ''}):
* status: new => needs_review
* author: => Michael Orlitzky
* cc: novoselt (added)
* dependencies: => #19368
* branch: => u/mjo/ticket/19405
* commit: => 0c1176c68504468baaeb754756c5808e49a5fcc5
Old description:
> The Lyapunov rank measures the length of a `lyapunov_like_basis()` and
> quantifies how many equations you can get out of the complementarity
> condition `<x,s> = 0`. Counting a basis is easy but unnecessarily slow
> when, for example, you have a single ray in a 100-dimensional space.
>
> The new `lyapunov_rank()` method computes the rank using a shortcut based
> on considering that single ray as living in its own span. Then the
> remaining 99-dimensions worth of zeros are easily dealt with.
>
> The operation of "considering the ray as living in its own span" is a bit
> tricky, and can only be done up to linear isomorphism. A private helper
> method `_restrict_to_space()` handles that.
>
> This is new stuff, but I've presented it to the department
> (http://michael.orlitzky.com/presentations
> /the_lyapunov_rank_of_an_improper_cone_-_part_i_-_algorithms.pdf) and a
> few people have even read the preprint. Perhaps more importantly, there's
> a doctest that checks the answer against the naive algorithm:
> `len(K.lyapunov_like_basis())`. So I'm Pretty Sure it works.
New description:
Last one in this series, I promise.
The Lyapunov rank measures the length of a `lyapunov_like_basis()` and
quantifies how many equations you can get out of the complementarity
condition `<x,s> = 0`. Counting a basis is easy but unnecessarily slow
when, for example, you have a single ray in a 100-dimensional space.
The new `lyapunov_rank()` method computes the rank using a shortcut based
on considering that single ray as living in its own span. Then the
remaining 99-dimensions worth of zeros are easily dealt with.
The operation of "considering the ray as living in its own span" is a bit
tricky, and can only be done up to linear isomorphism. A private helper
method `_restrict_to_space()` handles that.
This is new stuff, but I've presented it to the department
(http://michael.orlitzky.com/presentations
/the_lyapunov_rank_of_an_improper_cone_-_part_i_-_algorithms.pdf) and a
few people have even read the preprint. Perhaps more importantly, there's
a doctest that checks the answer against the naive algorithm:
`len(K.lyapunov_like_basis())`. So I'm Pretty Sure it works.
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=88b74bba339c1ff53063ebe43819b222fd478f1b
88b74bb]||{{{Trac #19332: Add discrete_complementarity_set() method for
cones.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=5852e1ccc9a362dbb577798961deb3958458cfc5
5852e1c]||{{{Trac #19332: Use reviewer's implementation of
discrete_complementarity_set().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=872932952e7db998d013637636ca82124ace544e
8729329]||{{{Trac #19332: Documentation updates for
discrete_complementarity_set().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=75b2f438073042e310adbcaea224959ba5f2105f
75b2f43]||{{{Trac #19332: Return a cached tuple from
discrete_complementarity_set().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=371714c6914b5392d5ee0b10df35fef48130809b
371714c]||{{{Trac #19368: Add LL() method for polyhedral closed convex
cones.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=30476c7ac05393358aa0eb7a3304a8eb8ac76e00
30476c7]||{{{Trac #19368: Rename LL() to lyapunov_like_basis().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8bda4c2134f5e6460c6ce9bae5e0ba96679e54c3
8bda4c2]||{{{Trac #19368: Clarify trivial cone/space doctest for
lyapunov_like_basis().}}}||
||[http://git.sagemath.org/sage.git/commit/?id=0c1176c68504468baaeb754756c5808e49a5fcc5
0c1176c]||{{{Trac #19405: Add _restrict_to_space() and lyapunov_rank()
methods for cones.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19405#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
