New issue

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

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

Already on GitHub? Sign in to your account

A fast zero-testing method is needed #10279

Open
MooVI opened this Issue Dec 17, 2015 · 3 comments

Comments

Projects
None yet
2 participants
@MooVI
Contributor

MooVI commented Dec 17, 2015

On occasion it is necessary to test if a symbolic expression is identically zero; for example in the row reduction algorithm rref where this issue arose (see #10120). Currently our best method is to apply simplify and see whether the expression reduces to zero. This is not ideal as simplify is very slow.

Quoting @asmeurer from the above issue:

'Zero equivalence is an impossible problem in general (see Richardson's Theorem). For restricted classes of functions it is computable (e.g., for rational functions). I my opinion the only completely right way to solve this is to have domains for matrices, e.g., a matrix over QQ(x) would only allow rational functions in x with rational number coefficients as its entries. This domain would know how to solve its own zero equivalence, and the most efficient way to do it (with the right representation, zero equivalence becomes trivial).'

This is one possible solution when one knows the domain, though this would be a large task to implement.

The other possible approach which would work less exactly but more generally and which should be easier to implement (and faster?) is to randomly evaluate the expression at several points. This is the approach Mathematica claims to use: 'Zero testing for various functions is done using symbolic transformations and interval-based numerical approximations after random numerical values have been substituted for variables.'

I envisage such a function first testing for obviously zero or non-zero expressions, then performing minimal simplification to get the expression in a form suitable for numerical evaluation at random values of the symbols involved, using chop=True or some cleverer method to tell if the function is zero. Obviously the issue would be with numerical stability, which is not a problem I have any experience with.

@moorepants

@MooVI

This comment has been minimized.

Contributor

MooVI commented Dec 17, 2015

Forgot to add, as brought up by moorepants, the issue #9121 is also relevant.

@asmeurer

This comment has been minimized.

Member

asmeurer commented Dec 19, 2015

I believe equals does this @smichr.

@MooVI

This comment has been minimized.

Contributor

MooVI commented Dec 19, 2015

@asmeurer Whoever wrote solve_linear_system (possibly @smichr ?) clearly considered .equals(0) too slow/unstable, but maybe it is now good enough. From an inline comment:

                    # We need to know if this is always zero or not. We
                    # assume that if there are free symbols that it is not
                    # identically zero (or that there is more than one way
                    # to make this zero). Otherwise, if there are none, this
                    # is a constant and we assume that it does not simplify
                    # to zero XXX are there better (fast) ways to test this?
                    # The .equals(0) method could be used but that can be
                    # slow; numerical testing is prone to errors of scaling.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment