fredrik-johansson
Adding Fmpz mpoly #59, cont.
I've merged master into #59 and have started pouring over the changes. I've done a small refactor of the context cache to just get myself acquainted with the code base more than anything else. Not married to those changes. I've also written up a small state of the PR.
This PR aims to supersede #59.
State of the PR
Existing files and flintlib completeness
Here's all the modified files from this PR
modified setup.py
modified src/flint/__init__.py
modified src/flint/flint_base/flint_base.pxd
modified src/flint/flint_base/flint_base.pyx
modified src/flint/flint_base/flint_context.pyx
modified src/flint/flintlib/fmpq.pxd
modified src/flint/flintlib/fmpz_mpoly.pxd
modified src/flint/pyflint.pxd
modified src/flint/test/__main__.py
modified src/flint/test/test.py
modified src/flint/types/fmpq.pxd
modified src/flint/types/fmpq.pyx
modified src/flint/types/fmpz_mpoly.pxd
modified src/flint/types/fmpz_mpoly.pyx
modified src/flint/types/fmpz_poly.pxd
new file src/flint/flintlib/fmpq_mpoly.pxd
new file src/flint/flintlib/fmpq_mpoly_factor.pxd
new file src/flint/flintlib/fmpz_mpoly_factor.pxd
new file src/flint/flintlib/fmpz_mpoly_q.pxd
new file src/flint/fmpq_mpoly.pyx
new file src/flint/types/fmpq_mpoly.pxd
new file src/flint/types/fmpq_mpoly.pyx
new file src/flint/types/fmpz_mpoly_q.pxd
new file src/flint/types/fmpz_mpoly_q.pyx
Of these, there are some build/meta related or unimportant changes, these are
modified setup.py
modified src/flint/__init__.py
modified src/flint/flint_base/flint_context.pyx
modified src/flint/flintlib/fmpq.pxd
modified src/flint/pyflint.pxd
modified src/flint/test/__main__.py
modified src/flint/test/test.py
modified src/flint/types/fmpq.pxd
modified src/flint/types/fmpq.pyx
modified src/flint/types/fmpz_poly.pxd
The changes that are of substance, in my opinion, are
new file src/flint/flintlib/fmpq_mpoly.pxd
new file src/flint/flintlib/fmpq_mpoly_factor.pxd
new file src/flint/flintlib/fmpz_mpoly_factor.pxd
new file src/flint/flintlib/fmpz_mpoly_q.pxd
new file src/flint/types/fmpq_mpoly.pxd
new file src/flint/types/fmpq_mpoly.pyx
modified src/flint/types/fmpz_mpoly.pxd
modified src/flint/types/fmpz_mpoly.pyx
new file src/flint/types/fmpz_mpoly_q.pxd
new file src/flint/types/fmpz_mpoly_q.pyx
With three of the remaining being unsubstantial
modified src/flint/flintlib/fmpz_mpoly.pxd
modified src/flint/flint_base/flint_base.pxd
modified src/flint/flint_base/flint_base.pyx
The remaining file is an odd one, this is a duplicate file name, but it's contents differ significantly from src/flint/types/fmpq_mpoly.pyx. It's also an odd one out with the project structure. The other file makes references to fmpz_mpoly, leading me to believe it is a scratch file. src/flint/types/fmpq_mpoly.pyx is much newer and src/flint/fmpq_mpoly.pyx only appears in one commit.
new file src/flint/fmpq_mpoly.pyx
From this, the scope of this PR seems to be
-
Add Cython declarations of the C functions for
-
fmpq_mpoly.h,new file src/flint/flintlib/fmpq_mpoly.pxd new file src/flint/types/fmpq_mpoly.pxd new file src/flint/types/fmpq_mpoly.pyx -
fmpq_mpoly_factor.h,new file src/flint/flintlib/fmpq_mpoly_factor.pxd -
fmpz_mpoly_factor.h,new file src/flint/flintlib/fmpz_mpoly_factor.pxd -
and
fmpz_mpoly_q.h,new file src/flint/flintlib/fmpz_mpoly_q.pxd new file src/flint/types/fmpz_mpoly_q.pxd new file src/flint/types/fmpz_mpoly_q.pyx
python-flintalready includes support forfmpz_mpoly.h.It also appears to contain a small refactor of the existing
fmpz_mpolymodules to account for the newmpoly's.modified src/flint/types/fmpz_mpoly.pxd modified src/flint/types/fmpz_mpoly.pyxUsing a couple snippets of elisp to assess the completeness of the
flintlibfiles based on the publicly documented functions -
(setq my/rst-regexs
`(("functions" . ,(rx (: bol ".. function:: " (+ (not whitespace)) " " (group (+ (not whitespace))) "(" (+ not-newline) eol)))
("types" . ,(rx (: bol ".. type:: " (group (+ not-newline)) eol)))))
(setq my/python-flint-rst-files
'(("fmpz_mpoly_q.rst" . "fmpz_mpoly_q.pxd")
("fmpz_mpoly_factor.rst" . "fmpz_mpoly_factor.pxd")
("fmpq_mpoly_factor.rst" . "fmpq_mpoly_factor.pxd")
("fmpq_mpoly.rst" . "fmpq_mpoly.pxd")
("fmpz_mpoly.rst" . "fmpz_mpoly.pxd")
("fmpq.rst" . "fmpq.pxd")))
(setq my/flint-doc-dir "/home/jake/Uni/Honours/Thesis/flint/doc/source")
(setq my/python-flint-dir "/home/jake/Uni/Honours/Thesis/python-flint/src/flint/flintlib/")
(defun my/find-missing-rst-entries (regex source-file-name target-file-name)
(save-excursion
(let* ((rst-buffer (find-file-noselect source-file-name))
(py-buffer (find-file-noselect target-file-name))
(missing '()))
(with-current-buffer rst-buffer
(goto-char (point-min))
(let ((count 0))
(while (re-search-forward regex nil t)
(setq count (1+ count))
(let ((func (substring-no-properties(match-string 1))))
(with-current-buffer py-buffer
(goto-char (point-min))
(unless (search-forward func nil t)
(push func missing)))))
`(,missing . ,count))))))
(let ((result nil)
(summary nil))
(dolist (regex my/rst-regexs)
(push "" result)
(push "" summary)
(dolist (pair my/python-flint-rst-files)
(let ((missing
(my/find-missing-rst-entries
(cdr regex)
(file-name-concat my/flint-doc-dir (car pair))
(file-name-concat my/python-flint-dir (cdr pair)))))
(when (car missing)
(push (format "\t%s / %s: \n\t\t%s"
(car pair) (cdr pair) (string-join (car missing) "\n\t\t")) result))
(push (format "\t%s / %s, found: %d/%d"
(car pair) (cdr pair) (- (cdr missing) (length (car missing))) (cdr missing)) summary)))
(unless (eq (car result) "") (push (concat (car regex) ":") result))
(push (concat (car regex) ":") summary))
(concat "---- Summary ----\n" (string-join summary "\n") "\n---- Missing ----\n" (string-join result "\n")))
---- Summary ----
types:
fmpq.rst / fmpq.pxd, found: 2/2
fmpz_mpoly.rst / fmpz_mpoly.pxd, found: 4/6
fmpq_mpoly.rst / fmpq_mpoly.pxd, found: 4/4
fmpq_mpoly_factor.rst / fmpq_mpoly_factor.pxd, found: 2/2
fmpz_mpoly_factor.rst / fmpz_mpoly_factor.pxd, found: 2/2
fmpz_mpoly_q.rst / fmpz_mpoly_q.pxd, found: 2/2
functions:
fmpq.rst / fmpq.pxd, found: 78/80
fmpz_mpoly.rst / fmpz_mpoly.pxd, found: 124/150
fmpq_mpoly.rst / fmpq_mpoly.pxd, found: 100/100
fmpq_mpoly_factor.rst / fmpq_mpoly_factor.pxd, found: 10/10
fmpz_mpoly_factor.rst / fmpz_mpoly_factor.pxd, found: 10/10
fmpz_mpoly_q.rst / fmpz_mpoly_q.pxd, found: 22/23
---- Missing ----
types:
fmpz_mpoly.rst / fmpz_mpoly.pxd:
fmpz_mpoly_vec_t
fmpz_mpoly_vec_struct
functions:
fmpq.rst / fmpq.pxd:
_fmpq_fprint
fmpq_fprint
fmpz_mpoly.rst / fmpz_mpoly.pxd:
fmpz_mpoly_symmetric
fmpz_mpoly_symmetric_gens
fmpz_mpoly_buchberger_naive_with_limits
fmpz_mpoly_buchberger_naive
fmpz_mpoly_vec_autoreduction_groebner
fmpz_mpoly_vec_autoreduction
fmpz_mpoly_vec_is_autoreduced
fmpz_mpoly_vec_is_groebner
fmpz_mpoly_reduction_primitive_part
fmpz_mpoly_spoly
fmpz_mpoly_vec_set_primitive_unique
fmpz_mpoly_vec_randtest_not_zero
fmpz_mpoly_vec_set_length
fmpz_mpoly_vec_insert_unique
fmpz_mpoly_vec_append
fmpz_mpoly_vec_set
fmpz_mpoly_vec_fit_length
fmpz_mpoly_vec_swap
fmpz_mpoly_vec_print
fmpz_mpoly_vec_clear
fmpz_mpoly_vec_init
fmpz_mpoly_primitive_part
fmpz_mpoly_set_fmpz_poly
fmpz_mpoly_get_fmpz_poly
fmpz_mpoly_is_fmpz_poly
fmpz_mpoly_fprint_pretty
fmpz_mpoly_q.rst / fmpz_mpoly_q.pxd:
fmpz_mpoly_q_set_str_pretty
I think that's quite good, those functions doesn't seem necessary, and any new ones will be easy to add on demand. I've done similar with all functions however it's quite long, and in my opinion, not of any use.
Outstanding comments
Both call methods for fmpz_mpoly and fmpq_mpoly are missing evalutation methods (__call__), some existing code is there, however commented out.
https://github.com/flintlib/python-flint/pull/59#issuecomment-1705199469
I'm also yet to look at @deinst's 6 commits on their initialize_fmpz branch, their other branches appear to be up to date.
I'll also aim to give an assessment of the outstanding comments on the old PR, I don't believe they are resolved.
MVP
When should we this PR to be complete? The core components of fmpz_mpoly, fmpq_mpoly, and fmpz_mpoly_q appear to be near complete, just lacking evaluation and the comments to be resolved. However, no work as been started on both of the factor modules, although the flintlib declarations exist.
Thanks @Jake-Moss for working on this (CC @deinst).
The CI failures are unrelated I think. Previously the 3.13-dev job was failing but here that seems to be fixed after CPython 3.13 alpha 6 was released yesterday.
The failures seen here for the macos jobs are separate. The ones in GitHub actions are I think failing because they use an older version of macos than is supported by our wheels (or something like that). The Cirrus CI job is I think failing because its config needs updating.
I already have fixes for both of those CI problems in gh-129 which I should really just merge but I need to at least update some docs (maybe I should just merge it anyway and improve later).
When should we this PR to be complete? The core components of
fmpz_mpoly,fmpq_mpoly, andfmpz_mpoly_qappear to be near complete, just lacking evaluation and the comments to be resolved. However, no work as been started on both of thefactormodules, although theflintlibdeclarations exist.
I'm fine with merging something with a view to adding further features later. I do want any added features to be consistent with other types and for everything to be well tested though.
I found that by writing tests that were generic across e.g. different poly types I ended up picking up on a lot of inconsistencies and bugs between the different types. It would be good to add the multivariate polynomial types here somehow even if only to test the behaviour of univariate polynomials in the multivariate representation: https://github.com/flintlib/python-flint/blob/1ce152dffc356af69b1d4c2ea0eb08854f3d733b/src/flint/test/test.py#L2430-L2449
Also as much as possible we should use generic tests for the multivariate polynomial types like fmpz_mpoly and fmpq_mpoly so that we are applying the same tests for both. This is important both for testing consistency and for making it easier to write the tests when future multivariate polynomial types are added. Adding tests like that leads to lots of small changes to make things more consistent.
You can measure test coverage using the bin/coverage.sh script or similar. Note that with the current setuptools build you need to force recythonisation for that to work like:
find src -name '*.c' -exec rm {} +
bin/coverage.sh
The meson build in gh-129 will probably handle that better but currently coverage is one of the features I haven't yet added to it...
We should aim for 100% coverage for the these new types. Here is what coverage gives right now:
coverage report --sort=cover
Name Stmts Miss Cover
------------------------------------------------------------
src/flint/types/fmpq_mpoly.pxd 2 2 0%
src/flint/types/fmpz.pxd 2 2 0%
src/flint/types/acb_series.pyx 582 573 2%
src/flint/types/fmpz_mpoly_q.pyx 74 71 4%
src/flint/types/arb_series.pyx 576 495 14%
src/flint/types/arb_poly.pyx 217 183 16%
src/flint/types/acb_poly.pyx 257 193 25%
src/flint/types/arf.pyx 107 76 29%
src/flint/flint_base/flint_context.pxd 8 4 50%
src/flint/types/dirichlet.pyx 57 25 56%
src/flint/types/fmpq_mpoly.pyx 353 154 56%
src/flint/types/fmpz_mpoly.pyx 422 159 62%
src/flint/types/arb_mat.pyx 313 111 65%
src/flint/types/fmpz_mpoly.pxd 10 3 70%
src/flint/types/acb_mat.pyx 370 108 71%
src/flint/test/__main__.py 77 17 78%
src/flint/types/arb.pyx 822 136 83%
src/flint/types/acb.pyx 893 139 84%
src/flint/flint_base/flint_base.pyx 129 17 87%
src/flint/functions/showgood.pyx 63 8 87%
src/flint/types/fmpz_series.pyx 189 13 93%
src/flint/types/fmpq_series.pyx 363 14 96%
src/flint/flint_base/flint_context.pyx 27 1 96%
src/flint/types/fmpq_poly.pyx 270 5 98%
src/flint/types/fmpq.pyx 229 4 98%
src/flint/types/fmpq_mat.pyx 247 4 98%
src/flint/types/nmod_mat.pyx 253 4 98%
src/flint/types/fmpz_poly.pyx 325 4 99%
src/flint/types/fmpz_mat.pyx 273 3 99%
src/flint/types/nmod_poly.pyx 254 2 99%
src/flint/types/fmpz_mod_poly.pyx 538 2 99%
src/flint/test/test.py 2616 7 99%
src/flint/types/fmpz.pyx 485 1 99%
src/flint/__init__.py 32 0 100%
src/flint/flint_base/__init__.py 0 0 100%
src/flint/functions/__init__.py 0 0 100%
src/flint/pyflint.pyx 3 0 100%
src/flint/test/__init__.py 0 0 100%
src/flint/types/__init__.py 0 0 100%
src/flint/types/fmpz_mod.pyx 210 0 100%
src/flint/types/fmpz_mod_mat.pyx 287 0 100%
src/flint/types/nmod.pyx 135 0 100%
src/flint/types/nmod_series.pyx 1 0 100%
src/flint/utils/__init__.py 0 0 100%
src/flint/utils/flint_exceptions.py 2 0 100%
------------------------------------------------------------
TOTAL 12073 2540 79%
For a wrapper library like python-flint line coverage is actually a pretty good baseline for measuring whether things are tested.
Particular things to play close attention to are type coercions e.g. fmpq * fmpz_mpoly and operations that are not always simply defined like division. Look carefully at how the existing types handle these. Note that other things have changed since gh-59 was first created e.g. gh-109.
Feel free to ask questions if you are unsure about anything. Also plenty of things can be improved so if something in the existing code does not seem right to you then say so!
Thanks for your response!
I've had a crack at adding partial application and function composition to the fmpz_mpoly.__call__ method. However I may have gotten over zealous and added context coercions for the composition before realising that the other methods explicitly disallow operations between polys from different contexts. So that leaves me with a couple of questions
- Should composition be allowed between polynomials from different contexts at all?
- If so should variables of the same name from different contexts be treated as the same? Code I've just pushed does this. Or should they be treated as different variables and thus renamed?
- When performing partial application, the resulting polynomial's context is not reduced/demoted, this gives (imo) the odd behaviour of not removing the applied variable from the context. Say you have the poly
z(x, y), in normal notation I would expectz(x)(y)to constitute two lots of partial application. If this notation is used with my current commit, because the context is not updated, the positional partial application fory, is actually reapplyingx. e.g.z(x, y) = x + y,z(1)(2) = y + 1, so- Should partial application reduce the context to remove the applied variables?
- Should partial application allow positional application at all? If only keyword args (as implemented) are allowed, this issue largely goes away.
- Should
python-flintbe worried about these implicit context conversions at all? I've seen some mention of what "level" this library should operate and I'm not sure where my changes would fit, definitely on the higher side though. I'd be happy to remove or refactor the current/add more explicit conversion methods that solve these problems.
I haven't thought about this too deeply but:
If our immediate goal is to get something partially complete that can be merged and improved upon later then it would be better to avoid all coercions etc for now and focus only on getting clearly well defined operations implemented and fully tested.
We want to avoid getting into a situation where conversions, coercions, context creation etc are taking place in inner loops or are being used unexpectedly. The best way to do that is just to give a TypeError. We also want to avoid implementing anything that turns out not to be so well defined later.
Creating contexts should be an operation that is allowed to be a little bit expensive so that other operations are kept fast by being able to reuse the existing contexts. As an example with fmpz_mod we have contexts but with nmod we do not. Having a context means that we can check whether the modulus is prime and store that information to check for operations where flint would otherwise abort. With nmod we don't have the context and it would slow things down to check whether the modulus is prime in every operation so we just don't check:
In [14]: flint.nmod_mat([[1, 2], [3, 4]], 6).rref()
Flint exception (Impossible inverse):
Cannot invert modulo 2*3
zsh: abort ipython
In general I think that python-flint needs to have more systematic handling of contexts and of explicit conversions. The way I would envisage that working though is that generally the user would be in control of the context objects and not that python-flint generates its own contexts behind the scenes.
It is possible that this is needed for something like polynomial composition though. I guess that it might be awkward to express some operations otherwise. I'm not sure what would be a good explicit interface for obtaining the result of the polynomial composition if it should go to a different context.
I would probably implement this so that the names of the symbols are actually just arbitrary hashable Python objects. Then when creating a context we do a hash lookup from the context cache and store the str of the symbols. If contexts are unique then comparing them in an operation like __add__ is just a pointer comparison and it doesn't matter what kind of objects the symbols are as long as they are hashable: their only role is the hash lookup when creating a context.
If our immediate goal is to get something partially complete that can be merged and improved upon later then it would be better to avoid all coercions etc for now and focus only on getting clearly well defined operations implemented and fully tested.
We want to avoid getting into a situation where conversions, coercions, context creation etc are taking place in inner loops or are being used unexpectedly. The best way to do that is just to give a TypeError. We also want to avoid implementing anything that turns out not to be so well defined later.
In general I think that python-flint needs to have more systematic handling of contexts and of explicit conversions. The way I would envisage that working though is that generally the user would be in control of the context objects and not that python-flint generates its own contexts behind the scenes.
Completely agree, I think that's quite reasonable for python-flint, provided it has an adequate API for handling explicit context conversions such that it is usable without reaching into python-flint. I think a reasonable interface might come from treating contexts more like types/subrings, and polynomials as objects of that type, then providing explicit up-casting/promotion and down-casting/demotion methods. This would, in some sense, allow the formalisation of these coercions. It does immediately raise a couple of question to me though. Should the x in R[x, y] be treated as the same x in R[x]? Or R[x, z]? Mathematically speaking it doesn't matter, x is just a label, or at least I consider them to be something more than isomorphic. So should contexts be characterised by only their number of variables and underlying field? What about ordering? Do we consider conversions between Z and Q separately?
I would probably implement this so that the names of the symbols are actually just arbitrary hashable Python objects. Then when creating a context we do a hash lookup from the context cache and store the
strof the symbols. If contexts are unique then comparing them in an operation like__add__is just a pointer comparison and it doesn't matter what kind of objects the symbols are as long as they are hashable: their only role is the hash lookup when creating a context.
Currently the context hash is a dictionary keyed by the number of variables, ordering (as a string), then a tuple of bytes representing the names of variables. It's currently possible to create a context and does not live in the context cache and to use it in methods, however the user facing method (flint_mpoly_context.get_context), does utilise the cache were possible. I think is comparison of contexts is pretty reasonable, if contexts are unique, and a context is not the same as the other context, it doesn't make sense to perform a computation between them.
It is possible that this is needed for something like polynomial composition though. I guess that it might be awkward to express some operations otherwise. I'm not sure what would be a good explicit interface for obtaining the result of the polynomial composition if it should go to a different context.
I added the implicit conversions because I found the behaviour jarring when composing with polys from different contexts, however I no longer agree with that. The joint context creation works by finding all the variables, collating them into a single context then performing a fmpz_mpoly_compose_fmpz_mpoly_gen on each of the polynomials to translate the variables into the new joint context. It assumes that variables of the same name are intended to be the same. It would be possible to also relabel them instead of merging them. However, I'll move the joint context creation and coercion into something explicit and refrain from adding more in this PR, perhaps that work will come later.
Composition between contexts without this joint context creation is actually not that bad, it just requires that all arguments of the composition share a context (which is what the joint context provides).
int fmpz_mpoly_compose_fmpz_mpoly(fmpz_mpoly_t A, const fmpz_mpoly_t B, fmpz_mpoly_struct *const *C, const fmpz_mpoly_ctx_t ctxB, const fmpz_mpoly_ctx_t ctxAC) Set A to the evaluation of B where the variables are replaced by the corresponding elements of the array C. Both A and the elements of C have context object ctxAC, while B has context object ctxB. ...
This does have a small issue for partial composition, the ctxAC will also need to contain the "uncomposed" variables, and then compose then as the trivial term. I don't see any other way to perform partial composition. I attempted to implement this, however I was completely unsatisfied my solution. I've marked it as not implemented.
When looking over the implementation of the __add__ operator and their reflected counterparts, I've noticed that they return NotImplemented for context incompatibility. This produces, imo, an unhelpful error message.
>>> import flint
>>> ctx = flint.fmpz_mpoly_ctx.get_context(1, "lex", "x")
>>> ctx2 = flint.fmpz_mpoly_ctx.get_context(1, "lex", "y")
>>> f = flint.fmpz_mpoly("x", ctx)
>>> g = flint.fmpz_mpoly("y", ctx2)
>>> f + g
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'flint.types.fmpz_mpoly.fmpz_mpoly' and 'flint.types.fmpz_mpoly.fmpz_mpoly'
The operand is support for fmpz_mpoly and fmpz_mpoly, it just happens that they live in incompatible contexts.
I understand the docs state that
If one of those methods does not support the operation with the supplied arguments, it should return NotImplemented. https://docs.python.org/3/reference/datamodel.html#object.add
However, I'd like to argue that we should instead raise a custom IncompatibleContextError, ValueError, or TypeError error which can provide more useful messages. While not a custom error, the ZeroDivisionError is already raised when appropriate.
I've implemented partial function composition for fmpz_mpoly, extracted the conversion and joint context creation methods into explicit methods, and disallowed positional partial application. Since the order of variables within a context is not stable during joint context construction, it's one giant walking gotcha.
Current usage for this looks like
>>> ctx = flint.fmpz_mpoly_ctx.get_context(2, "lex", "x, y")
>>> ctx1 = flint.fmpz_mpoly_ctx.get_context(2, "lex", "a, b")
>>> joint_ctx = flint.fmpz_mpoly_ctx.joint_context(ctx, ctx1)
>>> joint_ctx
fmpz_mpoly_ctx(4, 'lex', ('a', 'x', 'y', 'b'))
>>> z = flint.fmpz_mpoly("x^2 * y^2 + x * y", ctx)
>>> a = flint.fmpz_mpoly("20 * a * b", ctx1)
>>> z1 = z.coerce_to_context(joint_ctx)
>>> z1
x^2*y^2 + x*y
>>> a1 = a.coerce_to_context(joint_ctx)
>>> a1
20*a*b
>>> z1(y=a1)
400*a^2*x^2*b^2 + 20*a*x*b
Of course z and a could have been created in the joint context instead.
No tests other than my scratch notebook to date. Those will come next before I move this over to fmpq_mpoly as well.
I think a reasonable interface might come from treating contexts more like types/subrings, and polynomials as objects of that type, then providing explicit up-casting/promotion and down-casting/demotion methods. This would, in some sense, allow the formalisation of these coercions
I agree. There should be context objects for every type including fmpz and fmpq. Then there should be context methods like R.poly([1, 2, 3]) or R.matrix([[1, 2], [3, 4]]). It should be possible to retrieve the context associated to any object.
I am slightly wary about describing these as rings because there can be distinct contexts for the same mathematical ring (nmod vs fmpz_mod, Z[x,y] vs Z[y,x] etc) and also some cases like arb are not really rings. I think it is probably better to avoid trying to define mathematical spaces for things like matrices etc as well but we could still potentially have contexts for them and those could still be usable to create matrices like M.zeros(3, 4) or get the ground type like M.ground_type -> fZZ etc.
We can think of non matrix types as being associated with some mathematical ring and in so far as types represent the same ring or one is a subring or more generally they share a common subring then it should be possible to perform explicit conversions at least for elements of the common subring. The methods for doing this should allow for controlling the different possibilities like exact conversions vs homomorphic ones like fmpz -> nmod.
Should the
xinR[x, y]be treated as the samexinR[x]? OrR[x, z]? Mathematically speaking it doesn't matter,xis just a label, or at least I consider them to be something more than isomorphic. So should contexts be characterised by only their number of variables and underlying field? What about ordering? Do we consider conversions between Z and Q separately?
The context should represent the exact C level type as well as everything else like modulus for nmod, number of terms for series, variables for a polynomial ring, ordering etc. Ideally arb would have contexts representing precision (rather than using a global variable) or at least functions that take precision as an argument.
The question of what to do with symbols is a tricky one because if we have symbols for multivariate polynomials then it becomes natural to want them for univariate polynomials as well i.e. to have different fmpq_poly for Q[x] vs Q[y]. If we want to be able to perform implicit coercion between fmpq_mpoly and fmpq_poly while preserving some meaning of the symbols then we need a way to represent what symbol an fmpq_poly should be associated with.
Firstly we should ensure that there is a context for every type and that functions for explicit conversion that force full explicitness. A general interface for converting from one multivariate polynomial ring to another could use an explicit map like:
R1 = Q['x','y','z']
R2 = Q['t','x']
p1 = R1('x + 1')
p2 = R2.convert(p1, R1, {'x':'t'}) # p2 = t+1
If conversions are only done explicitly then exactly what should be considered as equivalent during a conversion is just an issue for the conversion function itself. If an explicit map is provided then it is for the user to define what notion of equivalence they want.
There can be different conversions that would be wanted in different situations. You might for example want to convert isomorphically from Q[x,y] -> Q[z,t] but with the understanding that x->z and y->t so the internal data structure is unchanged. You might on other hand want a different isomorphic conversion like Q[x,y] -> Q[y,x] that understands that it needs to reverse the internal ordering. You might also want a conversion like Q[x,y] -> Q[x] with the understanding that y=0 like your partial application which is a homomorphism rather than an isomorphism. You might also want a conversion like Q[x,y] -> Q[x] that would raise an error if the polynomial actually has any terms involving y.
There are situations that call for different kinds of conversion and so ideally you would have functions for each kind. Having a single global notion of "coercion" means having a global notion of what all objects represent outside of each particular type. So far python-flint has only had types where the global notion of what the objects are and how to convert between them is unambiguous but multivariate polynomials change that. In fact having multivariate polynomials even means that the existing univariate polynomials become ambiguous if there is any relationship between the two types of polynomials.
Another question I have considered is whether there should be explicit symbol objects like:
x = flint_symbol('x')
R = Q[x]
Having symbol objects would make it possible to intern them like contexts i.e. the argument to flint_symbol could be any hashable object. Then you can allow something like Q['x'] as a shorthand that internally uses flint_symbol('x'). Then users who just want to use strings as global symbols can do that but it is still possible to create distinct symbols that have the same name like flint_symbol(my_x, 'x').
Another possibility (for later) is that if conversion involves a significant amount of preprocessing before calling the underlying flint function then maybe it would be better to have converter objects like:
converter = R1.homorphism(R2, {x:z, y:t})
p1 = converter(p2)
Then if you need to do a lot of conversions you can make the converter once and use it repeatedly.
However, I'd like to argue that we should instead raise a custom
IncompatibleContextError
I agree. There is DomainError and we can also make more fine-grained exception types. This situation is analogous to nmod with different moduli which currently gives ValueError but DomainError would be better.
I think that introducing the concept of coercions whether explicit or implicit opens a big can of worms. All of python-flint's types (including future types) need to be considered before adding something like that.
Before coercion it would be better to have conversion e.g. functions or operations that can map from values of one type/context to values of another in a general and well defined way. For that we can have functions like:
R1 = Q[x,y,z]
R2 = Q[x,y]
p1 = R1('x + y')
# This is a partial function that would raise exceptions for some polynomials p1
p2 = p1.convert_to(R2, {x:x, y:y}) # R1('x + y')
# This is a well defined ring homomorphism
p1 = R1('x + y + z')
p2 = p1.eval_hom(R2, {z:1}, {x:x, y:y}) # R2('x+y+1')
# The final argument could be optional, raise if symbols don't match
p2 = p1.eval_hom(R2, {z:1}) # R2('x+y+1')
It would be more efficient if these operations are repeated to have converter and homomorphism objects something like:
p1 = R1('x + y + z')
hom = R1.homomorphism(R2, {x:x, y:y}, [z])
p2 = hom(p1, [1]) # R2('x+y+1')
p1 = R1('x+y')
to_R2 = R1.converter(R2, {x:x, y:y})
p2 = to_R2(p1) # R2('x+y')
I think that introducing the concept of coercions whether explicit or implicit opens a big can of worms.
Absolutely, and certainly out of scope for this PR at the moment. Though I really appreciate the thought put into these ideas. I think defining and separating conversions and the various morphisms has merit and I'll sit on it for a bit.
In the mean time I'll focus on getting tests for the existing code, mirroring it to fmpq_mpoly and test out the operations between univariate and multivariate polys. After that fmpq_mpoly_q will get my attention.
The Windows crashes are concerning.
Probably something to do with memory management...
The Windows crashes are concerning.
Probably something to do with memory management...
Agreed, it may related to the get and set item methods changing their behaviour depending on whether they're run under coverage or not
Unfortunately these commits did not resolve the get and set item test issues. They still pass normally, but failure under coverage. I'll take a closer look tonight.
I've also removed the coercions to fmpq_mpoly, unsure if this is the desired behaviour but it is consistent with the others I have written, easy to revert if not.
Hopefully that commit fixes the Windows and coverage test issues, a variable was being garbage collected when it's only reference was dropped. I believe this was only rearing its head in the coverages test because it gave the garbage collector just enough time to swoop in and destroy the python object, freeing the flint struct before I got a change to use it in the function call. A silly bug I went down quite the rabbit hole after (testing an updated version of the Cython GDB extensions and battling issues build Cython from source).
This also brings coverage to 83% for fmpz_mpoly. There's not many remaining statements to hit so I'll get them tomorrow as well as look at the from_dict function.
Hopefully that commit fixes the Windows and coverage test issues, a variable was being garbage collected when it's only reference was dropped.
That makes sense. The fix looks correct although I guess that we should also check if malloc returns NULL.
I would like to fix the other (unrelated) CI failures before merging this so we can see a full CI pass with the new types. The means merging gh-129 which I haven't done yet just because I wasn't sure if it would interrupt your workflow.
With meson-python you can make an editable build like
pip install --no-build-isolation --editable .
Then when you change the Cython code it rebuilds automatically at import time.
You can also use the spin frontend (pip install spin) to run e.g. spin test. Note that you can't combine these two things though so to use spin do not also have an editable install (and don't use spin install). One thing not implemented is spin coverage for measuring coverage of Cython code. It looks like for now we could just leave the setup.py in place and building the old way will still work though.
Can you try out gh-129 and let me know if it works for you?
If it is not going to break your workflow then I'll merge it and then we can see full CI runs for this PR.
That makes sense. The fix looks correct although I guess that we should also check if
mallocreturnsNULL.
Hmm, that's true we should be. There seems to be missing in a number of places this isn't checked. I'll add those today.
I would like to fix the other (unrelated) CI failures before merging this so we can see a full CI pass with the new types. The means merging gh-129 which I haven't done yet just because I wasn't sure if it would interrupt your workflow.
With meson-python you can make an editable build like
pip install --no-build-isolation --editable .Then when you change the Cython code it rebuilds automatically at import time.
You can also use the
spinfrontend (pip install spin) to run e.g.spin test. Note that you can't combine these two things though so to usespindo not also have an editable install (and don't usespin install). One thing not implemented isspin coveragefor measuring coverage of Cython code. It looks like for now we could just leave the setup.py in place and building the old way will still work though.Can you try out gh-129 and let me know if it works for you?
If it is not going to break your workflow then I'll merge it and then we can see full CI runs for this PR.
Certainly can, I'll let you know how it goes today. Spin seems interesting as well, I'll check it out.
I've been playing around with spin and meson-python for a couple hours now and they seem pretty good, I will be able to completely recreate my workflow. Though I did run into rather weird issues I wasn't able to resolve properly. Somewhere along the line of testing things meson-python completely broke jupyter, it was incredibly weird but if and only if I had python-flint installed via meson-python (through spin or not), jupyter would spew errors. I recreated my virtual environment and everything is working just fine now.
Migrating was quite easy, just need to set PKG_CONFIG_PATH correctly to my .local/lib64/pkgconfig directory. I'm using spin to "build" but not "install" python-flint, then launching things that need to know about python-flint via spin run.
The auto-compile on import is neat, though I much prefer seeing the compilation myself, particularly is something is 100% ok. Fortunately using spin build instead of spin install I'm able to have both, I can spin build --verbose from my editor and have it skip the compile on import if it's up to date. Though I'm not sure how to enable meson-pythons Verbose mode with spin, the env var doesn't work and it doesn't seem to provide an opt to it enable it. Perhaps I'll look into this further another day.
Maybe you're aware of this but, looking at the PR I don't see any options of the release builds. From what I've seen default optimisation level is -O0. I think this could be modified in the setup section of [tool.meson-python.args], but it should be noted that spin completely ignores that. Though arguments to meson can be provided in spin build, after removing the build directory.
I say merge it, almost everything works on my end and using the old setup.py for coverage is fine for now. I'll merge master once that's done. Also looks like the CI is still failing for windows, perhaps another memory issue, I'll take a closer look.
Thanks for testing gh-129. I've merged it now but there is a merge conflict here in test.py.
Migrating was quite easy, just need to set
PKG_CONFIG_PATHcorrectly to my.local/lib64/pkgconfigdirectory.
For some commands I need e.g.:
$ LD_LIBRARY_PATH=$(pwd)/.local/lib PKG_CONFIG_PATH=$(pwd)/.local/lib/pkgconfig spin test
It should only be necessary to set PKG_CONFIG_PATH once and then not bother with LD_LIBRARY_PATH but meson does not install the rpath. Maybe it needs an explicit install_rpath in the meson.buld file.
Maybe you're aware of this but, looking at the PR I don't see any options of the release builds. From what I've seen default optimisation level is
-O0
Maybe that is just a spin thing. I think if you build a wheel with python -m build or pip wheel . then the meson-python backend will use -O2.
You can also do meson setup --buildtype=release when using spin I think...
Maybe that is just a spin thing. I think if you build a wheel with
python -m buildorpip wheel .then the meson-python backend will use-O2.You can also do
meson setup --buildtype=releasewhen using spin I think...
Ah that makes sense.
Thanks for testing https://github.com/flintlib/python-flint/pull/129. I've merged it now but there is a merge conflict here in test.py.
I'll merge that in now thanks!
These windows test failures are annoying... they're failing at different points. I'll spin up a VM and see if I can replicate them.
- Using a couple snippets of elisp to assess the completeness of the
flintlibfiles based on the publicly documented functions
Note the bin/rst_to_pxd.py script that is used to make most .pxd files that declare flint functions.
I had a quick look through and I don't immediately see the cause of the Windows crash.
I think though that it would be better to try to reduce the use of malloc/free or rather to contain it to dedicated types. For example it would be good to have a Cython-level _fmpz_vec type that represents a variable length array of fmpz and could call fmpz_clear and free automatically. Probably all uses of malloc would be better hidden under types like that so that we can take maximum advantage of implicit memory management that Cython itself provides.
I think though that it would be better to try to reduce the use of malloc/free or rather to contain it to dedicated types. For example it would be good to have a Cython-level
_fmpz_vectype that represents a variable length array of fmpz and could callfmpz_clearandfreeautomatically. Probably all uses of malloc would be better hidden under types like that so that we can take maximum advantage of implicit memory management that Cython itself provides.
I think that's pretty reasonable, I'll migrate fmpz_mpoly to something of that description this week
I've got my Windows VM up and running everything installed and can reproduce the issue. However, gdb is being rather unhelpful and is not stopping at the segmentation fault, instead a thread is exiting with 4294967295 or 0xFFFFFFFF, which is not useful.
pytest by itself is being much nicer and reporting a line for when it fails, however, it's failing all over the place in fmpz_mpoly. I'll have to have a much closer reading again
There are a lot of commits here. Does it work on Windows with an older commit?
If so you could bisect.
With 4b08299 I can no longer reproduce the issue on my windows VM, I'll be interested to see how the CI fairs. Admittedly it was replacing some not-so-great code in the __call__ method, though I believed it was ok.
Either way, I've introduced two new types, fmpz_vec and fmpz_mpoly_vec, these are wrappers around their respective flint types with some convenience methods. fmpz_vec_t is a lot more featureful than what I've implemented but that could always be expanded later.
These objects have an additional parameter double_indirect, which enables the creation of another array with pointers to the underlying flint objects. This is a little clumsy however a lot of flint methods expect an fmpz_struct ** or fmpz_mpoly_struct ** argument.
Using these objects in methods like exponent_tuple, while useful, adds another copy to the overhead. I don't believe this can be avoided without adding a reference to fmpz to the underlying fmpz_vec otherwise the fmpz_vec could be deallocated while a fmpz that shares that data is alive. I'm hesitant to add this reference because it would have slightly unintuitive behaviour of two python objects sharing the same underlying mutable data. Although this is accepted in numpy and such
>>> import numpy as np
>>> a = np.arange(10)
>>> b = a[3:8]
>>> a[5] = 999
>>> b
array([ 3, 4, 999, 6, 7])
I've also updated the flintlib/fmpz_mpoly.pxd with the declarations from my copy of flint 3.1.2, which only has doc changes from 3.0.0
With 4b08299 I can no longer reproduce the issue on my windows VM, I'll be interested to see how the CI fairs.
CI is all green now!
That's a much better starting point to move forwards.
I'm hesitant to add this reference because it would have slightly unintuitive behaviour of two python objects sharing the same underlying mutable data
I'm not sure exactly what you mean by a reference here but in general we should treat a Cython fmpz instance as being immutable i.e. the only thing that ever happens to the C-level fmpz after it is created is that fmpz_clear will be called when the (Cython) fmpz's reference count drops to zero.
In general for other types (e.g. fmpz_mpoly) I am still not sure how useful mutability is. The SymPy equivalent for example are treated as immutable and any SymPy types that wrap these python-flint types will not mutate the poly/mpoly types.
my copy of flint 3.1.2
I must have missed the release announcement for this. We should update the version use for building wheels in CI.
I've also made progress in getting the coverage reports working with spin + meson. By adding
add_project_arguments('-X', 'linetrace=True', '-X', 'embedsignature=True', '-X', 'emit_code_comments=True', language : 'cython')
add_project_arguments('-DCYTHON_TRACE=1', language : 'c')
to python-flint/meson.build we can compile the cython with coverage support, then running
spin build --clean
spin test -c -- --cov-config=$(pwd)/.coveragerc
we can generate a report. I say a because it's not correct, the results are garbage, they say that things like __init__ methods were never called but some of the object methods were. I'm not sure where to even begin debugging this
---------- coverage: platform linux, python 3.12.1-final-0 -----------
Name Stmts Miss Cover
-------------------------------------------------------------------------------------------------------
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/flint_base/flint_base.pyx 143 69 52%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/flint_base/flint_context.pyx 27 21 22%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/acb.pyx 893 891 1%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/arb.pyx 822 814 1%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpq.pyx 229 155 32%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpq_mat.pyx 247 180 27%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpq_poly.pyx 270 176 35%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpq_series.pyx 363 167 54%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz.pyx 485 342 29%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_mat.pyx 273 150 45%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_mod.pyx 210 121 42%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_mod_mat.pyx 287 187 35%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_mod_poly.pyx 538 403 25%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_mpoly.pyx 552 461 16%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_poly.pyx 325 174 46%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/fmpz_series.pyx 189 132 30%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/nmod.pyx 135 112 17%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/nmod_mat.pyx 253 182 28%
/home/jake/Uni/Honours/Thesis/python-flint/src/flint/types/nmod_poly.pyx 254 142 44%
flint/__init__.py 33 0 100%
flint/flint_base/__init__.py 0 0 100%
flint/functions/__init__.py 0 0 100%
flint/test/__init__.py 0 0 100%
flint/test/__main__.py 77 77 0%
flint/test/test_all.py 2716 7 99%
flint/types/__init__.py 0 0 100%
flint/utils/__init__.py 0 0 100%
flint/utils/flint_exceptions.py 6 0 100%
-------------------------------------------------------------------------------------------------------
TOTAL 9327 4963 47%