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 )
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)
Change History (51)
comment:1 Changed 7 years ago by
- Description modified (diff)
comment:2 Changed 7 years ago by
- Description modified (diff)
comment:3 Changed 7 years ago by
- Cc malb added
comment:4 Changed 7 years ago by
- Reviewers set to Martin Albrecht
- Status changed from new to needs_review
comment:5 Changed 7 years ago by
- Status changed from needs_review to needs_work
comment:6 Changed 7 years ago by
patch and spkg updated
comment:7 Changed 7 years ago by
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
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
- Status changed from needs_work to needs_review
comment:10 Changed 7 years ago by
- 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
- Description modified (diff)
comment:12 Changed 7 years ago by
- Description modified (diff)
comment:13 Changed 7 years ago by
spkg updated (-fPIC and no compilation warnings)
comment:14 Changed 7 years ago by
- Status changed from needs_work to needs_review
comment:15 follow-up: ↓ 16 Changed 7 years ago by
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
Replying to malb:
Btw. is there an upstream repository/website?
https://bitbucket.org/fes/fes
It's fresh :)
comment:17 follow-up: ↓ 18 Changed 7 years ago by
And it's private, i.e., I cannot access it :)
comment:18 in reply to: ↑ 17 Changed 7 years ago by
comment:19 Changed 7 years ago by
Hi, can you reproduce the error I am seeing (above)?
comment:20 Changed 7 years ago by
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
- Dependencies set to #13202
comment:22 Changed 7 years ago by
@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
- 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
- Description modified (diff)
comment:25 Changed 7 years ago by
- Component changed from optional packages to experimental package
- Description modified (diff)
- Priority changed from minor to major
comment:26 Changed 7 years ago by
Hi martin,
ready for review :)
comment:27 Changed 7 years ago by
- 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
- 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
- Status changed from needs_review to positive_review
Looks good to me.
comment:30 Changed 7 years ago by
- 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
- 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
- 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
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
I have no idea what to do, maybe ask sage-devel?
comment:35 Changed 7 years ago by
- 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
@malb : getting positively reviewed again ?
comment:38 Changed 7 years ago by
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
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
- Status changed from positive_review to needs_work
comment:41 Changed 7 years ago by
All doctests in fes.pyx
need to be marked
# optional - fes
such that doctests succeed when libFES is not installed.
comment:42 follow-up: ↓ 43 Changed 7 years ago by
- 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
- 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
- Dependencies changed from #13202 to #13202,#13964
- Milestone changed from sage-5.6 to sage-5.7
comment:45 Changed 7 years ago by
- 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
I don't think you can (well, you can delete the files by hand of course).
comment:47 Changed 7 years ago by
@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
- Status changed from needs_review to positive_review
Yep, all tests pass. Sorry for the delay!
comment:49 Changed 7 years ago by
spkg is on the servers ...
comment:50 Changed 7 years ago by
- Merged in set to sage-5.7.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Hi, I found a few small issues (so far) :)
SPKG
hg status
in the SPKG reports files that are not checked in.Patch
exhaustive_search
has neither documentation nor doctests