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

Matrix.rank() incorrect results #9480

Closed
siefkenj opened this Issue Jun 7, 2015 · 17 comments

Comments

Projects
None yet
8 participants
@siefkenj
Copy link
Contributor

siefkenj commented Jun 7, 2015

There is an error in the Matrix.rank() function. It also appears to be in Matrix.rref().

m = Matrix([[-5 + 5*sqrt(2), -5], [-5*sqrt(2)/2 + 5, -5*sqrt(2)/2]])
print("shape:", m.shape)
print("det:", m.det())
print("rank:", m.rank())

outputs

shape: (2, 2)
det: 0
rank: 2

but should output

shape: (2, 2)
det: 0
rank: 1

Doing m.rank(simplify=True) gives the correct result, but if simplify=True is needed, m.rank() should at least throw some kind of warning to indicate that it might have computed the result incorrectly...

@toolforger

This comment has been minimized.

Copy link
Contributor

toolforger commented Jun 7, 2015

Was that limited to just PyPy, or does this happen with standard CPython as well?

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jun 7, 2015

This happens in pypy and all versions of cpython, AFAIK. I've tested on pypy 2.5, python 3.4, and python 2.7.5.

siefkenj added a commit to siefkenj/sympy that referenced this issue Jun 7, 2015

@toolforger

This comment has been minimized.

Copy link
Contributor

toolforger commented Jun 7, 2015

Good to know, thanks.
I can't fix it because I didn't write it and because I know far too little about matrices; can you look in git annotate who was last working on this? We can then ping that person (or persons), that should speed up the fixing process.

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jun 7, 2015

I'm sorry, I'm not that experienced with git. What exactly do you mean?

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jun 7, 2015

Looking at the Matrix.rref code, I see

if iszerofunc(r[pivot, i]):

and if this fails, the code acts like it isn't zero. However, x.is_zero returns True/False/None; None is returned when it cannot decide if the object is non-zero, and this is treated by the code as the object being non-zero even though its zero value cannot be determined...Doing this right might have some consequences though...For instance, the example that is included in the documentation Matrix([[1, 2], [x, 1 - 1/x]]).rref() should only be the identity matrix provided some assumptions on x (e.g., it is real and non-zero).

@toolforger

This comment has been minimized.

Copy link
Contributor

toolforger commented Jun 7, 2015

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jun 7, 2015

Looks like @smichr was most recently involved.

@hargup hargup added the matrices label Jun 22, 2015

@hargup

This comment has been minimized.

Copy link
Member

hargup commented Jun 22, 2015

@siefkenj Thanks for digging this up, adding a warning should be easy and you are welcome to make a PR.

Looking at the Matrix.rref code, I see

if iszerofunc(r[pivot, i]):

and if this fails, the code acts like it isn't zero. However, x.is_zero
returns True/False/None; None is returned when it cannot decide if the
object is non-zero, and this is treated by the code as the object being non-zero
even though its zero value cannot be determined...Doing this right might have
some consequences though...For instance, the example that is included in the
documentation Matrix([[1, 2], [x, 1 - 1/x]]).rref() should only be the
identity matrix provided some assumptions on x (e.g., it is real and
non-zero).

If the value of is_zero is None then we should raise an error, maybe a NotImplementedError saying cannot determine zero value for %s, then prompting the user to try again with simplify=True option. This too should be easy to fix.

@hargup hargup added the Easy to Fix label Jun 22, 2015

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jun 22, 2015

Doing this will presumably break several of the examples and unit tests. Should they be changed accordingly?

@toolforger

This comment has been minimized.

Copy link
Contributor

toolforger commented Jun 22, 2015

@jgrochow

This comment has been minimized.

Copy link

jgrochow commented Jun 30, 2015

Just as a note, this issue also comes up with matrices with polynomial entries, and I haven't found an example where simplify=True doesn't fix the problem...

gxyd pushed a commit to gxyd/sympy that referenced this issue Aug 8, 2015

Gaurav Dhingra
matrix.rank() with unkown `.is_zero` raise NotImplementedError
The failing tests have been marked `@xfail`
fixes issue sympy#9480

mcneela added a commit to mcneela/sympy that referenced this issue Aug 29, 2015

mcneela added a commit to mcneela/sympy that referenced this issue Aug 29, 2015

@gxyd gxyd referenced this issue Aug 29, 2015

Closed

Fixed Issue #9480 #9872

skirpichev added a commit to diofant/diofant that referenced this issue Sep 28, 2015

skirpichev added a commit to diofant/diofant that referenced this issue Sep 30, 2015

skirpichev added a commit to diofant/diofant that referenced this issue Sep 30, 2015

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Oct 29, 2015

If the value of is_zero is None then we should raise an error, maybe a NotImplementedError saying cannot determine zero value for %s, then prompting the user to try again with simplify=True option. This too should be easy to fix.

The problem is that it shouldn't raise an error if simplify=True is already given, and there's no way for iszerofunc to know what the value of that option is.

@ashutoshsaboo

This comment has been minimized.

Copy link
Contributor

ashutoshsaboo commented Jan 22, 2016

I want to work on this issue, and try resolving this! Is this solved? Can I try solving this?

rpisarev pushed a commit to rpisarev/sympy that referenced this issue Feb 22, 2016

Ruslan Pisarev
Fix sympy#9480
If some expresion does not contain symbols we can do _simplify() for that,
before comparing with zero.

       modified:   sympy/matrices/matrices.py
       modified:   sympy/matrices/tests/test_matrices.py
@rpisarev

This comment has been minimized.

Copy link
Contributor

rpisarev commented Apr 30, 2016

PR #10650 was updated to current master

skirpichev added a commit to skirpichev/diofant that referenced this issue Jun 15, 2016

Use Expr.equals to do zero-equivalence test in Matrix.rref
Fix is similar to sympy/sympy#10650, thanks to @rpisarev.  In case of
zero-decision problem - we raise NotImplementedError.

Closes diofant#288
Closes sympy/sympy#9480

(Maybe it fixes also sympy/sympy#11238)

See sympy/sympy#10280 for alternative.

skirpichev added a commit to skirpichev/diofant that referenced this issue Jun 15, 2016

Use Expr.equals to do zero-equivalence test in Matrix.rref
Fix is similar to sympy/sympy#10650, thanks to @rpisarev.  In case of
zero-decision problem - we raise NotImplementedError.

Closes diofant#288
Closes sympy/sympy#9480

(Maybe it fixes also sympy/sympy#11238)

See sympy/sympy#10280 for alternative.
@BrickMoon

This comment has been minimized.

Copy link

BrickMoon commented Jul 28, 2016

As has been said already, this is definitely related to the is_zero function returning None. Calling is_zero on this expression in particular returns None when it should return True:

expr = -5_sqrt(2)/2 + 5_(-5_sqrt(2)/2 + 5)/(-5 + 5_sqrt(2))

Is this correct behavior for sympy.core.add.Add? Is there a good reason why is_zero can't be determined for this expression? Seems weird to me that something this fundamental wouldn't be working correctly.

@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Jul 28, 2016

I think .is_zero is supposed to have low computational overhead. It returns None if it cannot decide without doing computations. I suspect the root of the problem is someone not thinking of this somewhere in the code. One should never write if not x.is_zero: for example, because that is different than if x.is_zero == False:

siefkenj added a commit to siefkenj/sympy that referenced this issue Aug 29, 2016

Impliment smart pivoting in `Matrix.rref`
	This patch addresses issues sympy#10718, sympy#9480, sympy#11434

	Now, during row reduction, when searching for
	a pivot, all elements are checked using
	is_zero.  If an element is proved to be non-zero,
	then it is used as a pivot.  If no elements can
	be proved to be non-zero, elements are simplified
	to see if one can be proved to be non-zero.  If
	that fails an assumption is made that one of the
	undetermined elements is non-zero.

	This patch also impliments partial pivoting if
	all entries in a matrix column are floats.
@siefkenj

This comment has been minimized.

Copy link
Contributor

siefkenj commented Sep 8, 2016

Resolved by PR #11554

@siefkenj siefkenj closed this Sep 8, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment