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

Possible bug in lusolve #437

Closed
josdejong opened this Issue Aug 24, 2015 · 8 comments

Comments

Projects
None yet
2 participants
@josdejong
Owner

josdejong commented Aug 24, 2015

Someone emailed me with the following case:

var Varr = [
    [ -1, 1, -1, 1 ],
    [ 0, 0, 0, 1 ],
    [ 1, 1, 1, 1 ],
    [ 8, 4, 2, 1 ] 
];

var x = [0.1, 0.2 , 0.15, 0.1];
var y1 = math.lusolve(Varr,x);
var y2 = math.multiply(math.inv(Varr),x);

console.log(math.multiply(Varr,y1)); // [ [ 0.1 ], [ 0.1 ], [ 0.15000000000000002 ], [ 0.2 ] ]
console.log(math.multiply(Varr,y2)); // [ 0.09999999999999998, 0.2, 0.15, 0.1 ]

both log statements should output the values of the original x, but it looks like lusolve is returning a wrong result for y1. I'm not sure if this is a bug or if I'm overlooking something obvious here. @rjbaucells do you have an idea?

@rjbaucells

This comment has been minimized.

Collaborator

rjbaucells commented Aug 24, 2015

The problem is related to the partial pivoting (row swap) that was required to solve the linear system. Performing the following operation will give you the actual permutations (P vector):

x = [0.2; 0.1; 0.15; 0.1]

r = math.lup(Varr)

p: [3, 0, 2, 1]

var y1 = math.lusolve(Varr, x)

Varr * y1 // [0.1; 0.1; 0.15; 0.2]

Applying row permutations to Varr * y1:

y2 = [0.2; 0.1; 0.15; 0.1]

Gives you the same column vector as x

This is something I will need to look in details with more time, I though lusolve() result was not affected by the row permutations...

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 25, 2015

Ok thanks, would be great if you can figure this out!

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 27, 2015

Some additional info:

If it helps the matrix is a special case of a Vandermonde matrix where each row is
[x^3 x^2 x 1]
for different values of x. Here x is -1, 0, 1 or 2.

I'm trying to fit cubic polynomials to some data and this a method for finding the coefficients.

@rjbaucells

This comment has been minimized.

Collaborator

rjbaucells commented Aug 27, 2015

Jos,

I found the root cause of the problem, as I though the partial pivoting does not affect the output of the lusolve() function. The problem is related to a bug in the permutation vector we are receiving from the lup() function. I will fix the problem and update the tests accordingly.

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 27, 2015

That's good news, thanks for the update!

rjbaucells added a commit to rjbaucells/mathjs that referenced this issue Aug 28, 2015

josdejong added a commit that referenced this issue Aug 28, 2015

Merge pull request #440 from rjbaucells/develop
Fix for issue #437 (Possible bug in lusolve)

@josdejong josdejong added the bug label Sep 13, 2015

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 29, 2015

@rjbaucells, we can close this issue right? Fix was merged.

@rjbaucells

This comment has been minimized.

Collaborator

rjbaucells commented Oct 31, 2015

Yes

@josdejong

This comment has been minimized.

Owner

josdejong commented Oct 31, 2015

thanks.

@josdejong josdejong closed this Oct 31, 2015

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