Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

dim(p) == fulldim(p), but volume(p) gives rank error #224

Closed
bzinberg opened this issue Oct 12, 2020 · 0 comments · Fixed by #228
Closed

dim(p) == fulldim(p), but volume(p) gives rank error #224

bzinberg opened this issue Oct 12, 2020 · 0 comments · Fixed by #228

Comments

@bzinberg
Copy link
Contributor

bzinberg commented Oct 12, 2020

In the example below, it looks like one of the simplices that is seen by the iterator in triangulation has too few vertices. Shouldn't this be guaranteed not to happen?

My immediate blocker is, I don't currently have a way to safely compute the volume of a polyhedron, because the method I'm currently using to detect degeneracy (dim < fulldim) fails here.

To reproduce:

julia> import LRSLib
julia> import Polyhedra
julia> p = Polyhedra.polyhedron(Polyhedra.convexhull([-5012508711568619//562949953421312, 583069911833861//562949953421312, 1219842180319805//35184372088832],
                                                     [-3609611117314485//1125899906842624, 5282286702292177//1125899906842624, 1219842180319805//35184372088832],
                                                     [-7725757995938945//1125899906842624, 1462211626014367//140737488355328, 1219842180319805//35184372088832],
                                                     [-532368590153764480371939662909266158793799405463504814709713817//77583810724479672721865369109640386986142477600327824161374208, 3224270984442009275405360045195456034995743746806217875031525951//310335242897918690887461476438561547944569910401311296645496832, 672457679454427424790403270603729873029078800097096746747208063//19395952681119918180466342277410096746535619400081956040343552],
                                                     [-99439783243032230401278200429697521956561640533421926702879//31016981899445501044376765532524576292400999567207920828416, 311994187972841311191238761811528823912588633689069650103080235//66500409192411154239143785301732691570907743072093782256123904, 288196148337611788210031345503791397986095421869031213993505867//8312551149051394279892973162716586446363467884011722782015488],
                                                     [-690806571294091770118800876784760427996256746750368522886675821//77583810724479672721865369109639134785033939652916888662441984, 321426694532486026572630868942976798207283537518053289963575445//310335242897918690887461476438556539140135758611667554649767936, 168114419863606861724632054332712979462833232159533470697926701//4848988170279979545116585569352445924064621228307305541402624],
                                                     [-1492392266911428135477270336942896864090819866924399644525722049//465502864346878027654888975401162411367555092311194971098054656, 8735837263239544956921962745120391980207061989984410077199166221//1862011457387512110619555901604649645470220369244779884392218624, 2017373038363282292032368858811720337472226359496354415171746909//58187858043359753456861121925145301420944386538899371387256832],
                                                     [-373098066727856630393118486909715763699958036549713602976647893//116375716086719509082798053664459230332289270193787821224886272, 1091979657904943666635059112885763141035648015680316821818842795//232751432173439018165596107328918460664578540387575642449772544, 2017373038363282329633298021940319932272991184557553168606931369//58187858043359754541399026832229615166144635096893910612443136],
                                                     [-7070582150880849//562949953421312, 3790773064745241//562949953421312, 1219842180319805//35184372088832],
                                                     [-34801539891522081227113644995895817371964429166316169581661393//2770850383017131220282711035205412611141700157032485986762752, 74633028634568024242096988893935168609715564253767685190029663//11083401532068524881130844140821650444566800628129943947051008, 6004086423700245009031028586285698644710591893089440485524287//173178148938570701267669439700338288196356259814530374172672],
                                                     [-15819997815895236991185625966444338695356530903287555618572799//1776728489873580456771017164550118143569876505199642857701376, 964280083597461551818957674899498352631347137057929931635288993//931005728693756159348012994224261907230615288724612857435521024, 1008686519181641264266253024289396959154227260201071539037865451//29093929021679879979625406069508184600956727772644151794860032],
                                                     [-2923329350887855490685984645262896737347750012999614732126096039//232751432173439018165596107328919516974055261816400618912219136, 6269174405303712066292933133855537629242176139218553155719560483//931005728693756072662384429315678067896221047265602475648876544, 1008686519181641142716748220931706730473386508489464675026988381//29093929021679877270699513416114939621756907727050077364027392]),
                                LRSLib.Library());
julia> (Polyhedra.dim(p), Polyhedra.fulldim(p))
(3, 3)
julia> Polyhedra.volume(p)
DimensionMismatch("matrix is not square: dimensions are (3, 2)")

Stacktrace:
 [1] checksquare at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/LinearAlgebra/src/LinearAlgebra.jl:223 [inlined]
 [2] det(::LinearAlgebra.LU{Rational{BigInt},Array{Rational{BigInt},2}}) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/LinearAlgebra/src/lu.jl:443
 [3] det(::Array{Rational{BigInt},2}) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/LinearAlgebra/src/generic.jl:1538
 [4] unscaled_volume_simplex(::Polyhedra.PointsHull{Rational{BigInt},Array{Rational{BigInt},1},Int64}) at /julia_projects/Polyhedra.jl/src/polyhedron.jl:59
[...]

[Edit: More information]
Calling removevredundancy!(p) before the call to volume does not get rid of the error.

bzinberg added a commit to bzinberg/Polyhedra.jl that referenced this issue Oct 31, 2020
bzinberg added a commit to bzinberg/Polyhedra.jl that referenced this issue Oct 31, 2020
bzinberg added a commit to bzinberg/Polyhedra.jl that referenced this issue Oct 31, 2020
bzinberg added a commit to bzinberg/Polyhedra.jl that referenced this issue Oct 31, 2020
blegat pushed a commit that referenced this issue Nov 26, 2020
* Add failing regression test for issue 224

#224

* Attempt to fix issue 224

#224

* Instead of incrementing `depth`, decrement `codim`

#228 (comment)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant