Date: Thursday, July 12, 2018 @ 14:25:43 Author: arojas Revision: 357920
Add patches for new eclib and cddlib Added: sagemath/trunk/sagemath-cddlib-094j.patch sagemath/trunk/sagemath-eclib-20180710.patch Modified: sagemath/trunk/PKGBUILD -------------------------------+ PKGBUILD | 13 sagemath-cddlib-094j.patch | 980 ++++++++++++++++++++++++++++++++++++++++ sagemath-eclib-20180710.patch | 24 3 files changed, 1014 insertions(+), 3 deletions(-) Modified: PKGBUILD =================================================================== --- PKGBUILD 2018-07-12 12:09:04 UTC (rev 357919) +++ PKGBUILD 2018-07-12 14:25:43 UTC (rev 357920) @@ -9,7 +9,7 @@ pkgbase=sagemath pkgname=(sagemath sagemath-jupyter) pkgver=8.2 -pkgrel=11 +pkgrel=12 pkgdesc="Open Source Mathematics Software, free alternative to Magma, Maple, Mathematica, and Matlab" arch=(x86_64) url="http://www.sagemath.org"; @@ -41,7 +41,8 @@ sagemath-detect-igraph.patch sagemath-networkx2.patch sagemath-scipy-1.0.patch sagemath-lrs.patch sagemath-singular-4.1.1.patch sagemath-lcalc-c++11.patch sagemath-gap-4.8.patch pari-ratpoints.patch::"https://github.com/sagemath/sage/commit/83458400.patch"; - sagemath-cypari2.patch::"https://git.sagemath.org/sage.git/patch?id=da380b32";) + sagemath-cypari2.patch::"https://git.sagemath.org/sage.git/patch?id=da380b32"; + sagemath-cddlib-094j.patch sagemath-eclib-20180710.patch) sha256sums=('41ba2c2dde7a02e1bb6880ae875d37ab058567cc26e760efe87eeb12188cd65b' 'b3c5f5c159d72ba7bc2b186b7b0e50a02b1ca60caef49b3857dbaad3da36b6fc' 'c41ae665499c6cd775d40bbe178f8786830b0931ee26bf11ee02f7d83bcc8107' @@ -61,7 +62,9 @@ '5114c912f821900e5bfae1e2cfeb7984de946d0b23e1182b0bf15be1d803dfd0' '6917cb74e50ae965ea8d7c39577e5f0a5068e4b6a67b53fc6f219149a7d06584' 'e24ad879f6b2eb970778fc5e867bcbe0a6d393feca8f11f5cb8d07da1f024be9' - '94847fc033fd36bc59217c8484d4cf48d0640ff35bb5ca5ffba88a8158c6dd44') + '94847fc033fd36bc59217c8484d4cf48d0640ff35bb5ca5ffba88a8158c6dd44' + '092a928b77c8bb1e23399f22be39f67797a0065954128b690ead6a09f9ce1e44' + '182b0765d58494978bf27628bada8b42c95ef7eb2671b91ddf9c67608560c662') prepare(){ cd sage-$pkgver @@ -104,6 +107,8 @@ patch -p1 -i ../sagemath-lcalc-c++11.patch # Adjust paths for gap-4.8 patch -p1 -i ../sagemath-gap-4.8.patch +# Fix build with eclib 20180710 + patch -p1 -i ../sagemath-eclib-20180710.patch # Upstream patches # fix build against libfes 0.2 http://trac.sagemath.org/ticket/15209 @@ -110,6 +115,8 @@ patch -p1 -i ../fes02.patch # update to cypari2 https://trac.sagemath.org/ticket/25813 patch -p1 -i ../sagemath-cypari2.patch +# port to cddlib 0.94j https://trac.sagemath.org/ticket/25344 + patch -p1 -i ../sagemath-cddlib-094j.patch # use python2 sed -e 's|#!/usr/bin/env sage-python23|#!/usr/bin/env python2|' -e 's|#!/usr/bin/env python\b|#!/usr/bin/env python2|' \ Added: sagemath-cddlib-094j.patch =================================================================== --- sagemath-cddlib-094j.patch (rev 0) +++ sagemath-cddlib-094j.patch 2018-07-12 14:25:43 UTC (rev 357920) @@ -0,0 +1,980 @@ +diff --git a/src/sage/geometry/polyhedron/backend_cdd.py b/src/sage/geometry/polyhedron/backend_cdd.py +index 9e0ca53ba7b..8497741b0c4 100644 +--- a/src/sage/geometry/polyhedron/backend_cdd.py ++++ b/src/sage/geometry/polyhedron/backend_cdd.py +@@ -154,7 +154,9 @@ def _init_from_cdd_input(self, cdd_input_string, cmdline_arg='--all', verbose=Fa + ....: [0.62, -1.38, 0.38],[0.144, -1.04, 0.04], + ....: [0.1309090909, -1.0290909091, 0.04]] + sage: Polyhedron(point_list) +- A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 14 vertices ++ Traceback (most recent call last): ++ ... ++ ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic. + sage: Polyhedron(point_list, base_ring=QQ) + A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices + """ +@@ -286,7 +288,9 @@ def cdd_adjacencies(): + else: + n_cdd=n; + self._V_adjacency_matrix = matrix(ZZ, n, n, 0) +- expect_in_cddout('begin') ++ if not find_in_cddout('begin'): ++ raise ValueError('Error while parsing cdd output: could not ' ++ 'find "begin" after "Vertex graph"') + l = cddout.pop(0).split() + assert int(l[0]) == n_cdd, "Not enough V-adjacencies in cdd output?" + for i in range(n_cdd): +@@ -309,7 +313,9 @@ def cdd_adjacencies(): + if find_in_cddout('Facet graph'): + n = len(self._Hrepresentation); + self._H_adjacency_matrix = matrix(ZZ, n, n, 0) +- expect_in_cddout('begin') ++ if not find_in_cddout('begin'): ++ raise ValueError('Error while parsing cdd output: could not ' ++ 'find "begin" after "Facet graph"') + l = cddout.pop(0).split() + assert int(l[0]) == n, "Not enough H-adjacencies in cdd output?" + for i in range(n): +--- +diff --git a/src/sage/geometry/hasse_diagram.py b/src/sage/geometry/hasse_diagram.py +index 9d336ce..c5bff21 100644 +--- a/src/sage/geometry/hasse_diagram.py ++++ b/src/sage/geometry/hasse_diagram.py +@@ -44,7 +44,7 @@ def Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, + implementation will just return these two tuples as a tuple; + + - ``required_atoms`` -- list of atoms (default:None). Each +- non-empty "face" requires at least on of the specified atoms ++ non-empty "face" requires at least one of the specified atoms + present. Used to ensure that each face has a vertex. + + - ``key`` -- any hashable value (default: None). It is passed down +diff --git a/src/sage/geometry/polyhedron/backend_cdd.py b/src/sage/geometry/polyhedron/backend_cdd.py +index 8497741..85f6632 100644 +--- a/src/sage/geometry/polyhedron/backend_cdd.py ++++ b/src/sage/geometry/polyhedron/backend_cdd.py +@@ -1,6 +1,19 @@ +-""" ++# -*- coding: utf-8 -*- ++r""" + The cdd backend for polyhedral computations + """ ++# **************************************************************************** ++# Copyright (C) 2011-2014 Volker Braun <vbraun.n...@gmail.com> ++# 2018 Timo Kaufmann <timo...@zoho.com> ++# 2018 Julian Rüth <julian.ru...@fsfe.org> ++# ++# This program is free software: you can redistribute it and/or modify ++# it under the terms of the GNU General Public License as published by ++# the Free Software Foundation, either version 2 of the License, or ++# (at your option) any later version. ++# https://www.gnu.org/licenses/ ++# **************************************************************************** ++ + from __future__ import print_function + from __future__ import absolute_import + +@@ -13,12 +26,10 @@ from .base import Polyhedron_base + from .base_QQ import Polyhedron_QQ + from .base_RDF import Polyhedron_RDF + +-######################################################################### + class Polyhedron_cdd(Polyhedron_base): +- """ ++ r""" + Base class for the cdd backend. + """ +- + def _init_from_Vrepresentation(self, vertices, rays, lines, verbose=False): + """ + Construct polyhedron from V-representation data. +@@ -49,8 +60,30 @@ class Polyhedron_cdd(Polyhedron_base): + """ + from .cdd_file_format import cdd_Vrepresentation + s = cdd_Vrepresentation(self._cdd_type, vertices, rays, lines) +- self._init_from_cdd_input(s, '--reps', verbose) +- ++ s = self._run_cdd(s, '--redcheck', verbose=verbose) ++ s = self._run_cdd(s, '--repall', verbose=verbose) ++ self._init_from_cdd_output(s) ++ if not self.base_ring().is_exact(): ++ # cdd's parser can not handle the full output of --repall, so we ++ # need to extract the first block before we feed it back into cdd ++ s = s.splitlines() ++ s = s[:s.index('end')+1] ++ s = '\n'.join(s) ++ t = self._run_cdd(s, '--rep', verbose=verbose) ++ ++ def parse(intro, data): ++ count = int(data[0][0]) ++ if count != len(self._cdd_V_to_sage_V): ++ # Upstream claims that nothing can be done about these ++ # cases/that they are features not bugs. Imho, cddlib is ++ # not really suitable for automatic parsing of its output, ++ # the implementation backed by doubles has not really been ++ # optimized for numerical stability, and makes some ++ # somewhat random numerical choices. (But I am not an ++ # expert in that field by any means.) See also ++ # https://github.com/cddlib/cddlib/pull/7. ++ raise ValueError("polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data") ++ Polyhedron_cdd._parse_block(t.splitlines(), 'V-representation', parse) + + def _init_from_Hrepresentation(self, ieqs, eqns, verbose=False): + """ +@@ -78,88 +111,32 @@ class Polyhedron_cdd(Polyhedron_base): + """ + from .cdd_file_format import cdd_Hrepresentation + s = cdd_Hrepresentation(self._cdd_type, ieqs, eqns) +- self._init_from_cdd_input(s, '--reps', verbose) +- +- +- def _init_facet_adjacency_matrix(self, verbose=False): +- """ +- Compute the facet adjacency matrix in case it has not been +- computed during initialization. +- +- INPUT: +- +- - ``verbose`` -- boolean (default: ``False``). Whether to print +- verbose output for debugging purposes. +- +- EXAMPLES:: +- +- sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], backend='cdd', base_ring=QQ) +- sage: '_H_adjacency_matrix' in p.__dict__ +- False +- sage: p._init_facet_adjacency_matrix() +- sage: p._H_adjacency_matrix +- [0 1 1] +- [1 0 1] +- [1 1 0] +- """ +- self._init_from_cdd_input(self.cdd_Hrepresentation(), +- '--adjacency', verbose) +- +- +- def _init_vertex_adjacency_matrix(self, verbose=False): +- """ +- Compute the vertex adjacency matrix in case it has not been +- computed during initialization. +- +- INPUT: +- +- - ``verbose`` -- boolean (default: ``False``). Whether to print +- verbose output for debugging purposes. +- +- EXAMPLES:: +- +- sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], backend='cdd', base_ring=QQ) +- sage: '_V_adjacency_matrix' in p.__dict__ +- False +- sage: p._init_vertex_adjacency_matrix() +- sage: p._V_adjacency_matrix +- [0 1 1] +- [1 0 1] +- [1 1 0] +- """ +- self._init_from_cdd_input(self.cdd_Vrepresentation(), +- '--adjacency', verbose) +- +- +- def _init_from_cdd_input(self, cdd_input_string, cmdline_arg='--all', verbose=False): +- """ +- Internal method: run cdd on a cdd H- or V-representation +- and initialize ourselves with the output. +- +- TESTS:: +- +- sage: p = Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0],[0,0,1]], +- ....: backend='cdd', base_ring=QQ) +- sage: from sage.geometry.polyhedron.cdd_file_format import cdd_Vrepresentation +- sage: s = cdd_Vrepresentation('rational', [[0,0,1],[0,1,0],[1,0,0]], [], []) +- sage: p._init_from_cdd_input(s) +- sage: p.dim() +- 2 +- +- sage: point_list = [[0.132, -1.028, 0.028],[0.5, 0.5, -1.5], +- ....: [-0.5, 1.5, -0.5],[0.5, 0.5, 0.5],[1.5, -0.5, -0.5], +- ....: [-0.332, -0.332, -0.668],[-1.332, 0.668, 0.332], +- ....: [-0.932, 0.068, 0.932],[-0.38, -0.38, 1.38], +- ....: [-0.744, -0.12, 1.12],[-0.7781818182, -0.12, 0.9490909091], +- ....: [0.62, -1.38, 0.38],[0.144, -1.04, 0.04], +- ....: [0.1309090909, -1.0290909091, 0.04]] +- sage: Polyhedron(point_list) +- Traceback (most recent call last): +- ... +- ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic. +- sage: Polyhedron(point_list, base_ring=QQ) +- A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices +- """ ++ s = self._run_cdd(s, '--redcheck', verbose=verbose) ++ s = self._run_cdd(s, '--repall', verbose=verbose) ++ self._init_from_cdd_output(s) ++ if not self.base_ring().is_exact(): ++ # cdd's parser can not handle the full output of --repall, so we ++ # need to extract the first block before we feed it back into cdd ++ s = s.splitlines() ++ s = s[:s.index('end')+1] ++ s = '\n'.join(s) ++ t = self._run_cdd(s, '--rep', verbose=verbose) ++ ++ def parse(intro, data): ++ count = int(data[0][0]) ++ infinite_count = len([d for d in data[1:] if d[0] == '1' and all(c == '0' for c in d[1:])]) ++ if count - infinite_count != len(self._Hrepresentation): ++ # Upstream claims that nothing can be done about these ++ # cases/that they are features not bugs. Imho, cddlib is ++ # not really suitable for automatic parsing of its output, ++ # the implementation backed by doubles has not really been ++ # optimized for numerical stability, and makes some ++ # somewhat random numerical choices. (But I am not an ++ # expert in that field by any means.) ++ raise ValueError("polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data") ++ Polyhedron_cdd._parse_block(t.splitlines(), 'H-representation', parse) ++ ++ def _run_cdd(self, cdd_input_string, cmdline_arg, verbose=False): + if verbose: + print('---- CDD input -----') + print(cdd_input_string) +@@ -175,157 +152,189 @@ class Polyhedron_cdd(Polyhedron_base): + if 'Error:' in ans + err: + # cdd reports errors on stdout and misc information on stderr + raise ValueError(ans.strip()) +- self._init_from_cdd_output(ans) ++ return ans ++ ++ @classmethod ++ def _parse_block(cls, cddout, header, parser): ++ r""" ++ Parse a block of cdd data identified by ``header`` by invoking ++ ``parser`` on it. ++ ++ EXAMPLES:: + ++ sage: cddout = r''' ++ ....: unrelated ++ ....: HEADER ++ ....: intro 0 1 2 ++ ....: begin ++ ....: data 0 1 2 ++ ....: data 3 4 5 ++ ....: end ++ ....: unrelated ++ ....: '''.splitlines() ++ sage: from sage.geometry.polyhedron.backend_cdd import Polyhedron_cdd ++ sage: def parser(intro, data): ++ ....: print("INTRO:", intro) ++ ....: print("DATA:", data) ++ sage: Polyhedron_cdd._parse_block(cddout, 'HEADER', parser) ++ INTRO: [['intro', '0', '1', '2']] ++ DATA: [['data', '0', '1', '2'], ['data', '3', '4', '5']] + +- def _init_from_cdd_output(self, cdd_output_string): ++ """ ++ try: ++ block = cddout[cddout.index(header)+1:] ++ except ValueError: ++ # section is missing in the cdd output ++ return ++ ++ intro = block[:block.index('begin')] ++ intro = [i.strip().split() for i in intro] ++ data = block[block.index('begin')+1:block.index('end')] ++ data = [d.strip().split() for d in data] ++ parser(intro, data) ++ ++ def _init_from_cdd_output(self, cddout): + """ + Initialize ourselves with the output from cdd. + + TESTS:: + +- sage: from sage.geometry.polyhedron.cdd_file_format import cdd_Vrepresentation +- sage: s = cdd_Vrepresentation('rational',[[0,0],[1,0],[0,1],[1,1]], [], []) +- sage: from subprocess import Popen, PIPE +- sage: cdd_proc = Popen(['cdd_both_reps_gmp', '--all'], stdin=PIPE, stdout=PIPE, stderr=PIPE) +- sage: ans, err = cdd_proc.communicate(input=s) +- sage: p = Polyhedron(vertices = [[0,0],[1,0],[0,1],[1,1]], backend='cdd', base_ring=QQ) +- sage: p._init_from_cdd_output(ans) ++ sage: p = Polyhedron(vertices = [[0,0],[1,0],[0,1],[1,1]], backend='cdd', base_ring=QQ) # indirect doctest + sage: p.vertices() + (A vertex at (0, 0), A vertex at (1, 0), A vertex at (0, 1), A vertex at (1, 1)) + """ +- cddout=cdd_output_string.splitlines() +- suppressed_vertex = False # whether cdd suppressed the vertex in output +- parent = self.parent() +- +- # nested function +- def expect_in_cddout(expected_string): +- l = cddout.pop(0).strip() +- if l!=expected_string: +- raise ValueError('Error while parsing cdd output: expected "' +- +expected_string+'" but got "'+l+'".\n') +- # nested function +- def cdd_linearities(): +- l = cddout[0].split() +- if l[0] != "linearity": +- return [] +- cddout.pop(0) +- assert len(l) == int(l[1])+2, "Not enough linearities given" +- return [int(i)-1 for i in l[2:]] # make indices pythonic +- +- # nested function +- def cdd_convert(string, base_ring=self.base_ring()): +- """ +- Converts the cdd output string to a numerical value. +- """ +- return [base_ring(x) for x in string.split()] +- +- # nested function +- def find_in_cddout(expected_string): +- """ +- Find the expected string in a list of strings, and +- truncates ``cddout`` to start at that point. Returns +- ``False`` if search fails. +- """ +- for pos in range(0,len(cddout)): +- l = cddout[pos].strip(); +- if l==expected_string: +- # must not assign to cddout in nested function +- for i in range(0,pos+1): +- cddout.pop(0) +- return True +- return False +- +- if find_in_cddout('V-representation'): ++ cddout = cddout.splitlines() ++ ++ def parse_indices(count, cdd_indices, cdd_indices_to_sage_indices=None): ++ cdd_indices = map(int, cdd_indices) ++ if cdd_indices_to_sage_indices is None: ++ cdd_indices_to_sage_indices = {i:i-1 for i in cdd_indices} ++ if count < 0: ++ assert cdd_indices_to_sage_indices is not None, "Did not expect negative counts here" ++ count = -count ++ cdd_indices = list(set(cdd_indices_to_sage_indices.keys()) - set(cdd_indices)) ++ assert count in [len(cdd_indices), len(cdd_indices) -1] ++ assert count == len(cdd_indices) ++ return [cdd_indices_to_sage_indices[i] for i in cdd_indices if cdd_indices_to_sage_indices[i] is not None] ++ ++ def parse_linearities(intro): ++ for entries in intro: ++ if entries and entries.pop(0) == 'linearity': ++ return parse_indices(int(entries.pop(0)), entries) ++ return [] ++ ++ def parse_H_representation(intro, data): ++ if '_Hrepresentation' in self.__dict__: ++ raise NotImplementedError("can not replace internal representation as this breaks caching") ++ self._Hrepresentation = [] ++ # we drop some entries in cdd's output and this changes the numbering; this dict keeps track of that ++ self._cdd_H_to_sage_H = {} ++ equations = parse_linearities(intro) ++ data[0].pop(2) # ignore data type, we know the base ring already ++ count, dimension = map(int, data.pop(0)) ++ assert self.ambient_dim() == dimension - 1, "Unexpected ambient dimension" ++ assert len(data) == count, "Unexpected number of lines" ++ for i, line in enumerate(data): ++ coefficients = map(self.base_ring(), line) ++ if coefficients[0] != 0 and all([e == 0 for e in coefficients[1:]]): ++ # cddlib sometimes includes an implicit plane at infinity: 1 0 0 ... 0 ++ # We do not care about this entry. ++ self._cdd_H_to_sage_H[i+1] = None ++ continue ++ ++ self._cdd_H_to_sage_H[i+1] = len(self._Hrepresentation) ++ if i in equations: ++ self.parent()._make_Equation(self, coefficients) ++ else: ++ self.parent()._make_Inequality(self, coefficients) ++ ++ self._Hrepresentation = tuple(self._Hrepresentation) ++ ++ def parse_V_representation(intro, data): ++ if '_Vrepresentation' in self.__dict__: ++ raise NotImplementedError("can not replace internal representation as this breaks caching") + self._Vrepresentation = [] +- lines = cdd_linearities() +- expect_in_cddout('begin') +- l = cddout.pop(0).split() +- assert self.ambient_dim() == int(l[1])-1, "Different ambient dimension?" +- suppressed_vertex = True +- for i in range(int(l[0])): +- l = cddout.pop(0).strip() +- l_type = l[0] +- l = l[1:] ++ # we drop some entries in cdd's output and this changes the numbering; this dict keeps track of that ++ self._cdd_V_to_sage_V = {} ++ lines = parse_linearities(intro) ++ data[0].pop(2) # ignore data type, we know the base ring already ++ count, dimension = map(int, data.pop(0)) ++ assert self.ambient_dim() == dimension - 1, "Unexpected ambient dimension" ++ assert len(data) == count, "Unexpected number of lines" ++ has_vertex = False ++ for i, line in enumerate(data): ++ kind = line.pop(0) ++ coefficients = map(self.base_ring(), line) ++ self._cdd_V_to_sage_V[i+1] = len(self._Vrepresentation) + if i in lines: +- parent._make_Line(self, cdd_convert(l)); +- elif l_type == '0': +- parent._make_Ray(self, cdd_convert(l)); ++ self.parent()._make_Line(self, coefficients); ++ elif kind == '0': ++ self.parent()._make_Ray(self, coefficients); + else: +- parent._make_Vertex(self, cdd_convert(l)); +- suppressed_vertex = False +- if suppressed_vertex and self.n_Vrepresentation()>0: +- # cdd does not output the vertex if it is only the origin +- parent._make_Vertex(self, [0] * self.ambient_dim()) ++ self.parent()._make_Vertex(self, coefficients) ++ has_vertex = True ++ if len(self._Vrepresentation) and not has_vertex: ++ # when the Polyhedron consists only of lines/rays from the ++ # origin, cddlib does not output the single vertex at the ++ # origin so we have to add it here as the Polyhedron class ++ # expects it to be there. ++ self.parent()._make_Vertex(self, [self.base_ring().zero()] * self.ambient_dim()) + self._Vrepresentation = tuple(self._Vrepresentation) +- expect_in_cddout('end') + +- if find_in_cddout('H-representation'): +- self._Hrepresentation = [] +- equations = cdd_linearities() +- expect_in_cddout('begin') +- l = cddout.pop(0).split() +- assert self.ambient_dim() == int(l[1])-1, "Different ambient dimension?" +- for i in range(int(l[0])): +- l = cddout.pop(0) +- if i in equations: +- parent._make_Equation(self, cdd_convert(l)); +- else: +- parent._make_Inequality(self, cdd_convert(l)); +- self._Hrepresentation = tuple(self._Hrepresentation) +- expect_in_cddout('end') +- +- # nested function +- def cdd_adjacencies(): +- l = cddout.pop(0).split() +- assert l[2] == ':', "Not a line of the adjacency data?" +- return [int(i)-1 for i in l[3:]] +- +- if find_in_cddout('Vertex graph'): +- n = len(self._Vrepresentation); +- if suppressed_vertex: +- n_cdd=n-1; +- else: +- n_cdd=n; +- self._V_adjacency_matrix = matrix(ZZ, n, n, 0) +- if not find_in_cddout('begin'): +- raise ValueError('Error while parsing cdd output: could not ' +- 'find "begin" after "Vertex graph"') +- l = cddout.pop(0).split() +- assert int(l[0]) == n_cdd, "Not enough V-adjacencies in cdd output?" +- for i in range(n_cdd): +- for a in cdd_adjacencies(): +- self._V_adjacency_matrix[i,a] = 1 ++ def parse_adjacency(intro, data, N, cdd_indices_to_sage_indices): ++ ret = matrix(ZZ, N, N, 0) ++ cdd_vertex_count = int(data.pop(0)[0]) ++ data.reverse() ++ for adjacencies in data: ++ assert adjacencies[2] == ':', "Not a line of adjacency data" ++ cdd_vertex = int(adjacencies[0]) ++ count = int(adjacencies[1]) ++ ++ # cdd sometimes prints implicit adjacencies for the plane at ++ # infinity at the end of the output (even though it's not part ++ # of the V/H representation) so we ignore indices that we do ++ # not know about. ++ if cdd_vertex not in cdd_indices_to_sage_indices: ++ cdd_indices_to_sage_indices[cdd_vertex] = None ++ v = cdd_indices_to_sage_indices[cdd_vertex] ++ if v is None: ++ continue ++ for w in parse_indices(count, adjacencies[3:], cdd_indices_to_sage_indices): ++ if w is None: ++ continue ++ ret[v, w] = 1 ++ return ret ++ ++ def parse_vertex_adjacency(intro, data): ++ if '_V_adjacency_matrix' in self.__dict__: ++ raise NotImplementedError("can not replace internal representation as this breaks caching") ++ N = len(self._Vrepresentation) ++ self._V_adjacency_matrix = parse_adjacency(intro, data, N, self._cdd_V_to_sage_V) ++ for i, v in enumerate(self._Vrepresentation): + # cdd reports that lines are never adjacent to anything. +- # I disagree, they are adjacent to everything! +- if self._Vrepresentation[i].is_line(): +- for j in range(n): ++ # we disagree, they are adjacent to everything. ++ if v.is_line(): ++ for j in range(len(self._Vrepresentation)): + self._V_adjacency_matrix[i,j] = 1 + self._V_adjacency_matrix[j,i] = 1 +- self._V_adjacency_matrix[i,i] = 0 +- if suppressed_vertex: # cdd implied that there is only one vertex +- for i in range(n-1): +- self._V_adjacency_matrix[i,n-1] = 1 +- self._V_adjacency_matrix[n-1,i] = 1 ++ self._V_adjacency_matrix[i,i] = 0 + self._V_adjacency_matrix.set_immutable() +- expect_in_cddout('end') +- +- if find_in_cddout('Facet graph'): +- n = len(self._Hrepresentation); +- self._H_adjacency_matrix = matrix(ZZ, n, n, 0) +- if not find_in_cddout('begin'): +- raise ValueError('Error while parsing cdd output: could not ' +- 'find "begin" after "Facet graph"') +- l = cddout.pop(0).split() +- assert int(l[0]) == n, "Not enough H-adjacencies in cdd output?" +- for i in range(n): +- for a in cdd_adjacencies(): +- self._H_adjacency_matrix[i,a] = 1 ++ self.vertex_adjacency_matrix.set_cache(self._V_adjacency_matrix) ++ ++ def parse_facet_adjacency(intro, data): ++ if '_H_adjacency_matrix' in self.__dict__: ++ raise NotImplementedError("can not replace internal representation as this breaks caching") ++ N = len(self._Hrepresentation) ++ self._H_adjacency_matrix = parse_adjacency(intro, data, N, self._cdd_H_to_sage_H) + self._H_adjacency_matrix.set_immutable() +- expect_in_cddout('end') ++ self.facet_adjacency_matrix.set_cache(self._H_adjacency_matrix) ++ ++ Polyhedron_cdd._parse_block(cddout, 'H-representation', parse_H_representation) ++ Polyhedron_cdd._parse_block(cddout, 'V-representation', parse_V_representation) ++ Polyhedron_cdd._parse_block(cddout, 'Facet adjacency', parse_facet_adjacency) ++ Polyhedron_cdd._parse_block(cddout, 'Vertex adjacency', parse_vertex_adjacency) + + +-######################################################################### + class Polyhedron_QQ_cdd(Polyhedron_cdd, Polyhedron_QQ): + """ + Polyhedra over QQ with cdd +@@ -350,7 +359,7 @@ class Polyhedron_QQ_cdd(Polyhedron_cdd, Polyhedron_QQ): + + _cdd_type = 'rational' + +- _cdd_executable = 'cdd_both_reps_gmp' ++ _cdd_executable = 'cddexec_gmp' + + def __init__(self, parent, Vrep, Hrep, **kwds): + """ +@@ -369,7 +378,6 @@ class Polyhedron_QQ_cdd(Polyhedron_cdd, Polyhedron_QQ): + Polyhedron_cdd.__init__(self, parent, Vrep, Hrep, **kwds) + + +-######################################################################### + class Polyhedron_RDF_cdd(Polyhedron_cdd, Polyhedron_RDF): + """ + Polyhedra over RDF with cdd +@@ -392,7 +400,7 @@ class Polyhedron_RDF_cdd(Polyhedron_cdd, Polyhedron_RDF): + """ + _cdd_type = 'real' + +- _cdd_executable = 'cdd_both_reps' ++ _cdd_executable = 'cddexec' + + def __init__(self, parent, Vrep, Hrep, **kwds): + """ +diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py +index 34f0a3f..a8ca502 100644 +--- a/src/sage/geometry/polyhedron/base.py ++++ b/src/sage/geometry/polyhedron/base.py +@@ -47,10 +47,9 @@ from sage.categories.sets_cat import EmptySetError + # * derive from Polyhedron_base + # + # * you must implement _init_from_Vrepresentation and +-# _init_from_Vrepresentationa ++# _init_from_Hrepresentation + # +-# * You might want to override _init_empty_polyhedron, +-# _init_facet_adjacency_matrix, _init_vertex_adjacency_matrix, and ++# * You might want to override _init_empty_polyhedron and + # _make_polyhedron_face. + # + # * You can of course also override any other method for which you +diff --git a/src/sage/geometry/polyhedron/library.py b/src/sage/geometry/polyhedron/library.py +index bbadbb3..2cdc728 100644 +--- a/src/sage/geometry/polyhedron/library.py ++++ b/src/sage/geometry/polyhedron/library.py +@@ -1100,18 +1100,23 @@ class Polytopes(): + + EXAMPLES:: + +- sage: td = polytopes.truncated_dodecahedron() # long time - 6secs +- sage: td.f_vector() # long time ++ sage: td = polytopes.truncated_dodecahedron() ++ sage: td.f_vector() + (1, 60, 90, 32, 1) +- sage: td.base_ring() # long time ++ sage: td.base_ring() + Number Field in sqrt5 with defining polynomial x^2 - 5 + +- A much faster implementation using floating point approximations:: ++ The faster implementation using floating point approximations does not ++ work unfortunately, see https://github.com/cddlib/cddlib/pull/7 for a ++ detailed discussion of this case:: + + sage: td = polytopes.truncated_dodecahedron(exact=False) +- sage: td.f_vector() ++ Traceback (most recent call last): ++ ... ++ ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data ++ sage: td.f_vector() # not tested + (1, 60, 90, 32, 1) +- sage: td.base_ring() ++ sage: td.base_ring() # not tested + Real Double Field + + Its faces are 20 triangles and 12 regular decagons:: +@@ -1323,21 +1328,25 @@ class Polytopes(): + sage: ti.base_ring() # long time + Number Field in sqrt5 with defining polynomial x^2 - 5 + +- A much faster implementation using floating point approximations:: ++ The faster implementation using floating point approximations does not ++ work unfortunately:: + + sage: ti = polytopes.truncated_icosidodecahedron(exact=False) +- sage: ti.f_vector() ++ Traceback (most recent call last): ++ ... ++ ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data ++ sage: ti.f_vector() # not tested + (1, 120, 180, 62, 1) +- sage: ti.base_ring() ++ sage: ti.base_ring() # not tested + Real Double Field + + Its faces are 30 squares, 20 hexagons and 12 decagons:: + +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 4) ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 4) # long time + 30 +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 6) ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 6) # long time + 20 +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 10) ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 10) # long time + 12 + """ + if base_ring is None and exact: +@@ -1382,26 +1391,32 @@ class Polytopes(): + + - ``backend`` -- the backend to use to create the polytope. + +- EXAMPLES:: ++ EXAMPLES: ++ ++ Unfortunately, no polyhedra backend supports the construction of the ++ snub dodecahedron at the moment:: + + sage: sd = polytopes.snub_dodecahedron() +- sage: sd.f_vector() ++ Traceback (most recent call last): ++ ... ++ ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic. ++ sage: sd.f_vector() # not tested + (1, 60, 150, 92, 1) +- sage: sd.base_ring() ++ sage: sd.base_ring() # not tested + Real Double Field + + Its faces are 80 triangles and 12 pentagons:: + +- sage: sum(1 for f in sd.faces(2) if len(f.vertices()) == 3) ++ sage: sum(1 for f in sd.faces(2) if len(f.vertices()) == 3) # not tested + 80 +- sage: sum(1 for f in sd.faces(2) if len(f.vertices()) == 5) ++ sage: sum(1 for f in sd.faces(2) if len(f.vertices()) == 5) # not tested + 12 + """ + if base_ring is None: + base_ring = RDF + phi = (1 + base_ring(5).sqrt()) / 2 +- xi = ((phi/2 + (phi - 5/27).sqrt()/2).nth_root(3) + +- (phi/2 - (phi - 5/27).sqrt()/2).nth_root(3)) ++ xi = ((phi/2 + (phi - 5/27).sqrt()/2)**(~ZZ(3)) + ++ (phi/2 - (phi - 5/27).sqrt()/2)**(~ZZ(3))) + + alpha = xi - 1 / xi + beta = xi * phi + phi**2 + phi / xi +@@ -1549,14 +1564,18 @@ class Polytopes(): + sage: gap # not tested - very long time + A 4-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^4 defined as the convex hull of 100 vertices + +- Computation with approximated coordinates is much faster:: ++ Computation with approximated coordinates would be much faster but is ++ not supported currently:: + + sage: gap = polytopes.grand_antiprism(exact=False) +- sage: gap ++ Traceback (most recent call last): ++ ... ++ ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data ++ sage: gap # not tested + A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 100 vertices +- sage: gap.f_vector() ++ sage: gap.f_vector() # not tested + (1, 100, 500, 720, 320, 1) +- sage: len(list(gap.bounded_edges())) ++ sage: len(list(gap.bounded_edges())) # not tested + 500 + """ + from itertools import product +diff --git a/src/sage/libs/ppl.pyx b/src/sage/libs/ppl.pyx +index 5366c74..e318e86 100644 +--- a/src/sage/libs/ppl.pyx ++++ b/src/sage/libs/ppl.pyx +@@ -110,14 +110,11 @@ basis vectors:: + sage: C_Polyhedron(gs) + A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 120 points + +-The above computation (using PPL) finishes without noticeable delay (timeit +-measures it to be 90 microseconds on sage.math). Below we do the same +-computation with cddlib, which needs more than 3 seconds on the same +-hardware:: ++The same computation with cddlib which is slightly slower:: + + sage: basis = list(range(5)) + sage: gs = [ tuple(coeff) for coeff in Permutations(basis) ] +- sage: Polyhedron(vertices=gs, backend='cdd') # long time (3s on sage.math, 2011) ++ sage: Polyhedron(vertices=gs, backend='cdd') + A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 120 vertices + + DIFFERENCES VS. C++ +diff --git a/src/sage/categories/finite_coxeter_groups.py b/src/sage/categories/finite_coxeter_groups.py +index e0b2846..8395895 100644 +--- a/src/sage/categories/finite_coxeter_groups.py ++++ b/src/sage/categories/finite_coxeter_groups.py +@@ -712,11 +712,15 @@ class FiniteCoxeterGroups(CategoryWithAxiom): + If function is too slow, switching the base ring to + :class:`RDF` will almost certainly speed things up. + +- EXAMPLES:: ++ EXAMPLES: ++ ++ Unfortunately, an inexact base ring can not always be used:: + + sage: W = CoxeterGroup(['H',3], base_ring=RDF) + sage: W.permutahedron() +- A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 120 vertices ++ Traceback (most recent call last): ++ ... ++ ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data + + sage: W = CoxeterGroup(['I',7]) + sage: W.permutahedron() +diff --git a/src/sage/geometry/polyhedron/backend_cdd.py b/src/sage/geometry/polyhedron/backend_cdd.py +index 85f6632..aaae546 100644 +--- a/src/sage/geometry/polyhedron/backend_cdd.py ++++ b/src/sage/geometry/polyhedron/backend_cdd.py +@@ -115,6 +115,10 @@ class Polyhedron_cdd(Polyhedron_base): + s = self._run_cdd(s, '--repall', verbose=verbose) + self._init_from_cdd_output(s) + if not self.base_ring().is_exact(): ++ if len(self._Vrepresentation) == 0: ++ # cdd (reasonably) refuses to handle empty polyhedra, so we ++ # skip this check ++ return + # cdd's parser can not handle the full output of --repall, so we + # need to extract the first block before we feed it back into cdd + s = s.splitlines() +diff --git a/src/sage/graphs/generators/smallgraphs.py b/src/sage/graphs/generators/smallgraphs.py +index bae02d7..084ed43 100644 +--- a/src/sage/graphs/generators/smallgraphs.py ++++ b/src/sage/graphs/generators/smallgraphs.py +@@ -4454,14 +4454,19 @@ def TruncatedIcosidodecahedralGraph(): + and 180 edges. For more information, see the + :wikipedia:`Truncated_icosidodecahedron`. + +- EXAMPLES:: ++ EXAMPLES: ++ ++ Unfortunately, this graph can not be constructed currently, due to numerical issues:: + + sage: g = graphs.TruncatedIcosidodecahedralGraph(); g +- Truncated Icosidodecahedron: Graph on 120 vertices +- sage: g.order(), g.size() ++ Traceback (most recent call last): ++ ... ++ ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic. ++ sage: g.order(), g.size() # not tested + (120, 180) + """ + from sage.geometry.polyhedron.library import polytopes ++ # note that dropping exact=False here makes the construction take forever + G = polytopes.icosidodecahedron(exact=False).truncation().graph() + G.name("Truncated Icosidodecahedron") + return G +-- +cgit v1.0-1-gd88e + + +From c4048677393f7088d1aa9a2c1392ed95d809d31c Mon Sep 17 00:00:00 2001 +From: =?UTF-8?q?Julian=20R=C3=BCth?= <julian.ru...@fsfe.org> +Date: Thu, 14 Jun 2018 12:00:27 +0200 +Subject: Relax cddlib sanity checks + +sometimes cddlib's output is useful even if it fails to transform back and forth +--- + src/sage/categories/finite_coxeter_groups.py | 9 ++--- + src/sage/geometry/polyhedron/backend_cdd.py | 6 ++- + src/sage/geometry/polyhedron/library.py | 56 +++++++++++++--------------- + 3 files changed, 33 insertions(+), 38 deletions(-) + +diff --git a/src/sage/categories/finite_coxeter_groups.py b/src/sage/categories/finite_coxeter_groups.py +index 8395895..78a89fd 100644 +--- a/src/sage/categories/finite_coxeter_groups.py ++++ b/src/sage/categories/finite_coxeter_groups.py +@@ -712,15 +712,14 @@ class FiniteCoxeterGroups(CategoryWithAxiom): + If function is too slow, switching the base ring to + :class:`RDF` will almost certainly speed things up. + +- EXAMPLES: +- +- Unfortunately, an inexact base ring can not always be used:: ++ EXAMPLES:: + + sage: W = CoxeterGroup(['H',3], base_ring=RDF) + sage: W.permutahedron() +- Traceback (most recent call last): ++ doctest:warning + ... +- ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data ++ UserWarning: This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies. ++ A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 120 vertices + + sage: W = CoxeterGroup(['I',7]) + sage: W.permutahedron() +diff --git a/src/sage/geometry/polyhedron/backend_cdd.py b/src/sage/geometry/polyhedron/backend_cdd.py +index aaae546..64f3002 100644 +--- a/src/sage/geometry/polyhedron/backend_cdd.py ++++ b/src/sage/geometry/polyhedron/backend_cdd.py +@@ -82,7 +82,8 @@ class Polyhedron_cdd(Polyhedron_base): + # somewhat random numerical choices. (But I am not an + # expert in that field by any means.) See also + # https://github.com/cddlib/cddlib/pull/7. +- raise ValueError("polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data") ++ from warnings import warn ++ warn("This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies.") + Polyhedron_cdd._parse_block(t.splitlines(), 'V-representation', parse) + + def _init_from_Hrepresentation(self, ieqs, eqns, verbose=False): +@@ -137,7 +138,8 @@ class Polyhedron_cdd(Polyhedron_base): + # optimized for numerical stability, and makes some + # somewhat random numerical choices. (But I am not an + # expert in that field by any means.) +- raise ValueError("polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data") ++ from warnings import warn ++ warn("This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies.") + Polyhedron_cdd._parse_block(t.splitlines(), 'H-representation', parse) + + def _run_cdd(self, cdd_input_string, cmdline_arg, verbose=False): +diff --git a/src/sage/geometry/polyhedron/library.py b/src/sage/geometry/polyhedron/library.py +index 2cdc728..1115978 100644 +--- a/src/sage/geometry/polyhedron/library.py ++++ b/src/sage/geometry/polyhedron/library.py +@@ -1106,25 +1106,27 @@ class Polytopes(): + sage: td.base_ring() + Number Field in sqrt5 with defining polynomial x^2 - 5 + +- The faster implementation using floating point approximations does not +- work unfortunately, see https://github.com/cddlib/cddlib/pull/7 for a +- detailed discussion of this case:: +- +- sage: td = polytopes.truncated_dodecahedron(exact=False) +- Traceback (most recent call last): +- ... +- ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data +- sage: td.f_vector() # not tested +- (1, 60, 90, 32, 1) +- sage: td.base_ring() # not tested +- Real Double Field +- + Its faces are 20 triangles and 12 regular decagons:: + + sage: sum(1 for f in td.faces(2) if len(f.vertices()) == 3) + 20 + sage: sum(1 for f in td.faces(2) if len(f.vertices()) == 10) + 12 ++ ++ The faster implementation using floating point approximations does not ++ fully work unfortunately, see https://github.com/cddlib/cddlib/pull/7 ++ for a detailed discussion of this case:: ++ ++ sage: td = polytopes.truncated_dodecahedron(exact=False) ++ doctest:warning ++ ... ++ UserWarning: This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies. ++ sage: td.f_vector() ++ Traceback (most recent call last): ++ ... ++ KeyError: ... ++ sage: td.base_ring() ++ Real Double Field + """ + if base_ring is None and exact: + from sage.rings.number_field.number_field import QuadraticField +@@ -1328,25 +1330,21 @@ class Polytopes(): + sage: ti.base_ring() # long time + Number Field in sqrt5 with defining polynomial x^2 - 5 + +- The faster implementation using floating point approximations does not +- work unfortunately:: ++ The implementation using floating point approximations is much faster:: + + sage: ti = polytopes.truncated_icosidodecahedron(exact=False) +- Traceback (most recent call last): +- ... +- ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data +- sage: ti.f_vector() # not tested ++ sage: ti.f_vector() + (1, 120, 180, 62, 1) +- sage: ti.base_ring() # not tested ++ sage: ti.base_ring() + Real Double Field + + Its faces are 30 squares, 20 hexagons and 12 decagons:: + +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 4) # long time ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 4) + 30 +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 6) # long time ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 6) + 20 +- sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 10) # long time ++ sage: sum(1 for f in ti.faces(2) if len(f.vertices()) == 10) + 12 + """ + if base_ring is None and exact: +@@ -1564,18 +1562,14 @@ class Polytopes(): + sage: gap # not tested - very long time + A 4-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^4 defined as the convex hull of 100 vertices + +- Computation with approximated coordinates would be much faster but is +- not supported currently:: ++ Computation with approximated coordinates is much faster:: + + sage: gap = polytopes.grand_antiprism(exact=False) +- Traceback (most recent call last): +- ... +- ValueError: polyhedron data is numerically complicated; cdd could not convert between inexact V and H representation without loss of data +- sage: gap # not tested ++ sage: gap + A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 100 vertices +- sage: gap.f_vector() # not tested ++ sage: gap.f_vector() + (1, 100, 500, 720, 320, 1) +- sage: len(list(gap.bounded_edges())) # not tested ++ sage: len(list(gap.bounded_edges())) + 500 + """ + from itertools import product +-- +cgit v1.0-1-gd88e Added: sagemath-eclib-20180710.patch =================================================================== --- sagemath-eclib-20180710.patch (rev 0) +++ sagemath-eclib-20180710.patch 2018-07-12 14:25:43 UTC (rev 357920) @@ -0,0 +1,24 @@ +diff --git a/src/sage/libs/eclib/wrap.cpp b/src/sage/libs/eclib/wrap.cpp +index 5fd5693b53..d12468faa8 100644 +--- a/src/sage/libs/eclib/wrap.cpp ++++ b/src/sage/libs/eclib/wrap.cpp +@@ -133,8 +133,8 @@ char* Curvedata_isogeny_class(struct Curvedata* E, int verbose) + + + int mw_process(struct Curvedata* curve, struct mw* m, +- const struct bigint* x, const struct bigint* y, +- const struct bigint* z, int sat) ++ const bigint* x, const bigint* y, ++ const bigint* z, int sat) + { + Point P(*curve, *x, *y, *z); + if (!P.isvalid()) +@@ -188,7 +188,7 @@ int mw_rank(struct mw* m) + } + + /* Returns index and unsat long array, which user must deallocate */ +-int mw_saturate(struct mw* m, struct bigint* index, char** unsat, ++int mw_saturate(struct mw* m, bigint* index, char** unsat, + long sat_bd, int odd_primes_only) + { + vector<long> v;
