Opened 7 years ago

Closed 7 years ago

#13162 closed enhancement (fixed)

add experimental libFES package

Reported by: Bouillaguet Owned by: malb
Priority: major Milestone: sage-5.7
Component: packages: experimental Keywords:
Cc: malb Merged in: sage-5.7.beta1
Authors: Charles Bouillaguet Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13202 Stopgaps:

Description (last modified by Bouillaguet)

libfes is a library (under development) that solves systems of boolean equations by exhaustive search. It is dramatically faster than Groebner bases in general.

Installation Guide

  • Download the fes-0.1 spkg here
  • Apply fes.2.patch to the sage library
  • Test:
    sage: from sage.libs.fes import exhaustive_search
    sage: R.<x,y,z> = BooleanPolynomialRing()
    sage: f = [x*y + z + y + 1, x+y+z, x*y + y*z]
    sage: ideal(f).variety()
    sage: exhaustive_search(f)
    

Note to release manage the SPKG should be added to the experimental repository, but the patch should be applied to Sage.

Attachments (1)

fes.2.patch (14.8 KB) - added by Bouillaguet 7 years ago.
new patch, because the library interface has changed

Download all attachments as: .zip

Change History (51)

comment:1 Changed 7 years ago by Bouillaguet

  • Description modified (diff)

comment:2 Changed 7 years ago by Bouillaguet

  • Description modified (diff)

comment:3 Changed 7 years ago by Bouillaguet

  • Cc malb added

comment:4 Changed 7 years ago by malb

  • Reviewers set to Martin Albrecht
  • Status changed from new to needs_review

Hi, I found a few small issues (so far) :)

SPKG

  • little error in SPKG.txt
      === mypackage-0.1 (Charles Bouillaguet, 25 June 2012) ===
    
  • hg status in the SPKG reports files that are not checked in.
  • please include the Trac ticket number in the SPKG.txt changelog (and the hg commit message of your SPKG)

Patch

  • since FES is a library its interface should live in sage.libs.fes and not sage.rings.polynomial.fes
  • exhaustive_search has neither documentation nor doctests

comment:5 Changed 7 years ago by malb

  • Status changed from needs_review to needs_work

comment:6 Changed 7 years ago by Bouillaguet

patch and spkg updated

comment:7 Changed 7 years ago by malb

Hi, almost there IMHO:

  • the docstring isn't properly formated:
    • INPUT shouldn't get a double ":" but a single one
    • AFAIK the argument list after input should look like
      INPUT:
      
       - ``foo`` - description
      
    • There shouldn't be leading "#" in your comments between code blocks, indentation does take care of it
    • sage: blocks should be indented by four spaces wrt to the preceding block ending with :: this includes the comments in between these code blocks
  • who frees dense_rep_eqs?

comment:8 Changed 7 years ago by Bouillaguet

Hi,

patch modified again (use the second one, not the first one). I updated the docstrings according to the standard. Also, *NOW*, dense_rep_eqs is freed :)

comment:9 Changed 7 years ago by Bouillaguet

  • Status changed from needs_work to needs_review

comment:10 Changed 7 years ago by malb

  • Status changed from needs_review to needs_work

SPKG

  • This looks bad:
wrapper.c: In function ‘exhaustive_search_wrapper’:
wrapper.c:17:5: warning: implicit declaration of function ‘exhaustive_ia32’ [-Wimplicit-function-declaration]
wrapper.c:23:5: warning: implicit declaration of function ‘exhaustive_simd’ [-Wimplicit-function-declaration]
  • You should add "-fPIC" to CFLAGS in spkg-install, it won't compile without it (on my machine)

Patch

  • Your patch was incorrectly indented, I fixed this in the updated patch attached to this ticket.

comment:11 Changed 7 years ago by malb

  • Description modified (diff)

comment:12 Changed 7 years ago by Bouillaguet

  • Description modified (diff)

comment:13 Changed 7 years ago by Bouillaguet

spkg updated (-fPIC and no compilation warnings)

comment:14 Changed 7 years ago by Bouillaguet

  • Status changed from needs_work to needs_review

comment:15 follow-up: Changed 7 years ago by malb

I still get:

main_simd.c: In function ‘main’:
main_simd.c:58:3: warning: implicit declaration of function ‘exhaustive_simd’ [-Wimplicit-function-declaration]

Btw. is there an upstream repository/website?

comment:16 in reply to: ↑ 15 Changed 7 years ago by Bouillaguet

Replying to malb:

Btw. is there an upstream repository/website?

https://bitbucket.org/fes/fes

It's fresh :)

comment:17 follow-up: Changed 7 years ago by malb

And it's private, i.e., I cannot access it :)

comment:18 in reply to: ↑ 17 Changed 7 years ago by Bouillaguet

Replying to malb:

And it's private, i.e., I cannot access it :)

fixed

comment:19 Changed 7 years ago by malb

Hi, can you reproduce the error I am seeing (above)?

comment:20 Changed 7 years ago by Bouillaguet

Yes, I could. I corrected it "upstream" :). I am currently in Taïwan, notably to develop this thing with my colleagues here, so that it should change a lot in the next days. I will tell you when it stabilizes a bit (i.e. when we stop spending consecutive whole days working on it...)

comment:21 Changed 7 years ago by Bouillaguet

  • Dependencies set to #13202

comment:22 Changed 7 years ago by Bouillaguet

@malb : you [c/s]hould download again the .spkg (which has changed), and apply the new patch, after applying Alexander's patch in #13202. You will see a notable performance improvement (and higher degrees are supported as well)

comment:23 Changed 7 years ago by Bouillaguet

  • Component changed from commutative algebra to optional packages
  • Milestone changed from sage-5.2 to sage-5.3

comment:24 Changed 7 years ago by Bouillaguet

  • Description modified (diff)

comment:25 Changed 7 years ago by Bouillaguet

  • Component changed from optional packages to experimental package
  • Description modified (diff)
  • Priority changed from minor to major

comment:26 Changed 7 years ago by Bouillaguet

Hi martin,

ready for review :)

comment:27 Changed 7 years ago by malb

  • Status changed from needs_review to needs_work

Hi Charles, sorry being so late in my reply:

  • line 2: Sage is spelled Sage not SAGE, in fact "Binding for the FES library" should be sufficient, that this is for Sage is kind of obvious
  • You define exhaustive_search as {{{cpdef}}} but you don't specify input and output types, defeating the purpose of having it callable from C
  • If it that function ought to be a Python function then perhaps max_sols should accept infinity as a parameter for "no restriction". It's what the SAT solver interface in Sage does.
  • I'd swap {{{verbose}}} and {{{max_sols}}} because {{{max_sols}}} changes the behaviour in a more fundamental way than {{{verbose}}}.
  • One can also specify verbosity with {{{set_verbose}}}, if you like {{{verbose}}} as a parameter better for some reason, no strict need to change it, most people don't use {{{set/get_verbose}}} in their code it seems.
  • "The order in which the solutions are returned is implementation dependent" if that's the case, then the doctests need to take that into account, i.e., they have the order hard coded at the moment. You could run sorted() on the output (in the doctests)
  • You can run PLE decomposition on your matrix (see sage.matrix.matrix_mod2_dense) which is a generalisation of LU and is very fast because it's implemented in M4RI
  • Isn't there some restriction for the number of variables?

comment:28 Changed 7 years ago by Bouillaguet

  • Status changed from needs_work to needs_review

Hi Martin,

patch updated. Regarding the PLE decomposition, these functions are not used presently (the library would need to be updated first), but they were useful to develop the library...

comment:29 Changed 7 years ago by malb

  • Status changed from needs_review to positive_review

Looks good to me.

comment:30 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

I know it's a detail, but better do it right: the indentation is sloppy. Sometimes, the indent is 4 spaces, other times 3 spaces. Please always use 4 spaces per indentation level.

comment:31 Changed 7 years ago by Bouillaguet

  • Status changed from needs_work to needs_review
  • Summary changed from add experimental libfes package to add experimental libFES package

indentation has been fixed. Why does the emacs Pyrex-mode that ships with sage does this ?!? (I use TAB to indent...)

comment:32 Changed 7 years ago by jdemeyer

  • Status changed from needs_review to needs_work

The documentation doesn't build properly:

/release/merger/sage-5.6.beta1/devel/sage/doc/en/reference/sage/libs/fes.rst:11: WARNING: autodoc can't import/find module 'sage.libs.fes', it reported error: "No module named fes", please check your spelling and sys.path

comment:33 Changed 7 years ago by Bouillaguet

Martin, Jeroen,

My understanding is that this is caused by the conditional inclusion of the cython module to the Sage library, depending on whether the actual spkg has been installed. I thought that this was the way to go for experimental packages. But apparently, it prevents me from including stuff in the reference manual.

What should I do ? Unconditionally include the python code to the SAGE library and mark all the doctests as optional ?

comment:34 Changed 7 years ago by jdemeyer

I have no idea what to do, maybe ask sage-devel?

comment:35 Changed 7 years ago by Bouillaguet

  • Status changed from needs_work to needs_review

I gave up on modifying the reference manual. This will likely be accessible through martin's #13850, which makes me happy enough

comment:36 Changed 7 years ago by Bouillaguet

@malb : getting positively reviewed again ?

comment:37 Changed 7 years ago by malb

  • Status changed from needs_review to positive_review

Yep

comment:38 Changed 7 years ago by jdemeyer

There are uncommitted changes in the spkg:

jdemeyer@sage:~/spkg/fes-0.1$ hg status
M spkg-install

comment:39 Changed 7 years ago by jdemeyer

The following can be removed from spkg-install:

unset RM

INCLUDES="-I$SAGE_LOCAL/include"
LIBDIRS="-L$SAGE_LOCAL/lib"

And if $MAKE check actually does something, it should be inside spkg-check and not in spkg-install.

comment:40 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:41 Changed 7 years ago by jdemeyer

All doctests in fes.pyx need to be marked

# optional - fes

such that doctests succeed when libFES is not installed.

comment:42 follow-up: Changed 7 years ago by Bouillaguet

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I updated the spkg (taking into account Jeroen's comments).

I don't think that marking the doctests as optional is necessary, as the .pyx file is NOT included in the source tree when the spkg is not installed (cf. magic in module_list.py).

However, the more I think about this, the more I am convinced that the right way to access this library from sage is through #13850. In that case, the doctest involving libFES in the documentation of .solve() would need to be marked optional, of course.

comment:43 in reply to: ↑ 42 Changed 7 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to Bouillaguet:

I updated the spkg (taking into account Jeroen's comments).

I don't think that marking the doctests as optional is necessary, as the .pyx file is NOT included in the source tree when the spkg is not installed (cf. magic in module_list.py).

That's not true. The module_list.py magic is only about compiling the Cython file, which is completely orthogonal to doctests. The fes.pyx file is always there (regardless of whether it is compiled), so the doctests are there.

comment:44 Changed 7 years ago by Bouillaguet

  • Dependencies changed from #13202 to #13202,#13964
  • Milestone changed from sage-5.6 to sage-5.7

Changed 7 years ago by Bouillaguet

new patch, because the library interface has changed

comment:45 Changed 7 years ago by Bouillaguet

  • Dependencies changed from #13202,#13964 to #13202
  • Status changed from needs_work to needs_review

Hi malb & Jeroen. OK, I get it now, sorry for the noise. I marked the doctests as optional and fixed the spkg.

Since I have installed the libFES package in my sage tree, I don't see how I could test without it? (how to uninstall a spkg ?).

comment:46 Changed 7 years ago by malb

I don't think you can (well, you can delete the files by hand of course).

comment:47 Changed 7 years ago by Bouillaguet

@malb : if you don't have the libFES spkg installed, can you check that this patch applies and passes the tests ?

comment:48 Changed 7 years ago by malb

  • Status changed from needs_review to positive_review

Yep, all tests pass. Sorry for the delay!

comment:49 Changed 7 years ago by schilly

spkg is on the servers ...

comment:50 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.7.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.