You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Gilles <gi...@harfang.homelinux.org> on 2016/10/29 13:46:25 UTC
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Hi.
This conversation should preferably be continued on the
"dev" ML.
[CC'ing there.]
Best regards,
Gilles
On Sat, 29 Oct 2016 13:43:43 +0200, Eric Barnhill wrote:
> Hi Wilbur,
>
> That is strange that such a basic technique appears to be at odds
> with best
> practices, especially when said best practice is out of numerical
> recipes,
> which has such broad authority.
>
> I think you would be welcome to push the change if you were
> interested to
> and your contribution would be welcome.
>
> Thank you also for citing the smile library. That appears to be an
> extraordinarily rich Java library. It is a good example of why
> projects
> need active, interested, expert maintainers; if code is not
> maintained by
> such a person it is generally quickly surpassed by other code
> elsewhere.
>
> Best,
> Eric
> Well, I tried the same with "Array2DRowRealMatrix" but it made no
> difference
> at all.
>
> Meanwhile I cloned the CM snapshot and checked the source code. The
> authors
> of the "LUDecomposition" class state that their code "is based on the
> class
> with similar name from the JAMA library" but this seems not the case!
> The
> Jama implementation is quite different -- actually the same as the
> alternate
> (Num. Recipes) implementation I had supplied earlier (and also runs
> at the
> expected speed)!
>
> So, whatever the reason was to abandon the JAMA version, the current
> Commons
> Math implementation is certainly much inferior in terms of
> performance.
> Which is astonishing given the popularity of this method.
>
> Will ask the "dev" mailing list, as suggested ...
>
> Thanks,
> Wilhelm
>
>
>
>
>
> --
> View this message in context: http://apache-commons.680414.
> n4.nabble.com/math-LU-decomposition-very-SLOW-commons-math3-linear-
> tp4692255p4692283.html
> Sent from the Commons - User mailing list archive at Nabble.com.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
Hi, I successully managed to post an issue on JIRA
(https://issues.apache.org/jira/browse/MATH-1390) and I am willing to fix
it. How does this issue get assigned? -- anything else I need to do? Sorry
for my ignorance ...
--Wilhelm
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692436.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
I second that, recalling some very rough API transitions/incompatibilities in
the past (e.g., around 'LeastSquaresOptimizer')...
--Wilhelm
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692482.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by Gilles <gi...@harfang.homelinux.org>.
On Fri, 4 Nov 2016 03:16:29 -0700 (PDT), wilbur wrote:
> Makes all sense. I will prepare a "minimally invasive" patch that
> exactly
> mimics the original behavior.
>
> In a possible future version, I think interfaces should be used from
> the
> beginning, even if there is only a small chance that different
> implementations arise. It is hard/impossible to resolve this later.
In CM, wherever there could have been interfaces, but there
aren't, was a conscious decision: it allowed to evolve the API
without breaking compatibility (e.g. adding methods).
This has come handy, since strangely enough, in CM the quality
of the design was somehow not considered on a par with the quality
of the implementations... [IOW, refactoring was frowned upon by
some even when it was the only reasonable solution to an issue!]
That's why, personally, I'd welcome attempts to improve on that
level, but I think that it should be done in new packages so that
it's possible to compare the respective merits of alternative
approaches.
Regards,
Gilles
>
> --Wilhelm
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
Makes all sense. I will prepare a "minimally invasive" patch that exactly
mimics the original behavior.
In a possible future version, I think interfaces should be used from the
beginning, even if there is only a small chance that different
implementations arise. It is hard/impossible to resolve this later.
--Wilhelm
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692477.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by Gilles <gi...@harfang.homelinux.org>.
Hello.
On Wed, 2 Nov 2016 05:32:50 -0700 (PDT), wilbur wrote:
> Hi Gilles,
>
> thanks for pointing me to the JIRA system - will try to do my best
> ;-)
>
> I am aware of the potential of breaking existing code with any such
> changes.
> However, expected problems seem to be minor in this case. Also, if
> existing
> code relies on such obvious design flaws it should be fixed as well.
> In
> particular:
>
> 1) If a 'null' result from getL(), getU() or getP() was sofar used to
> determine the singularity of the input matrix, the isNonSingular()
> method
> should have been called instead. Of course, this behaviour could
> still be
> preserved if needed.
It should probably be changed only as part of more thorough review
of all the decomposition classes.
See also
https://issues.apache.org/jira/browse/MATH-1049
https://issues.apache.org/jira/browse/MATH-1024
> 2) If, for some reason, getL(), getU() or getP() were called
> repeatedly --
> relying on the fact that they always return a reference to the SAME
> matrix
> -- this is dangerous practice and should be stopped. If needed, just
> bind
> the result from the first call to some variable.
It might have been assumed that in the majority of cases, there are
no "repeated" calls.
In this case, the extra copy is a performance loss, especially when
the matrix is large.
> 3) Making the inner 'Solver' class non-static should have no
> consequences
> for expernal code.
It looks so indeed.
> I also found some literal '(x == 0.0)' tests which should not be used
> in
> numerical code (something we teach our students in the first
> semester).
Some of them may be on purpose.
Check the "findbugs-exclude-filter.xml" file.
>
> At this moment I do not see the need for a new package. If a more
> extensive
> redesign is wanted,
Along the years, a major overhaul of the "linear" has been
discussed many times... [Cf. ML archive.]
> I suggest to use interfaces at the top level to allow
> for different concrete implementations. The same likely applies to
> other
> decompositions.
Ideally, I agree, but unless several implementations are
actually foreseen, it might not be worth it...
Regards,
Gilles
>
> --Wilhelm
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
Hi Gilles,
thanks for pointing me to the JIRA system - will try to do my best ;-)
I am aware of the potential of breaking existing code with any such changes.
However, expected problems seem to be minor in this case. Also, if existing
code relies on such obvious design flaws it should be fixed as well. In
particular:
1) If a 'null' result from getL(), getU() or getP() was sofar used to
determine the singularity of the input matrix, the isNonSingular() method
should have been called instead. Of course, this behaviour could still be
preserved if needed.
2) If, for some reason, getL(), getU() or getP() were called repeatedly --
relying on the fact that they always return a reference to the SAME matrix
-- this is dangerous practice and should be stopped. If needed, just bind
the result from the first call to some variable.
3) Making the inner 'Solver' class non-static should have no consequences
for expernal code.
I also found some literal '(x == 0.0)' tests which should not be used in
numerical code (something we teach our students in the first semester).
At this moment I do not see the need for a new package. If a more extensive
redesign is wanted, I suggest to use interfaces at the top level to allow
for different concrete implementations. The same likely applies to other
decompositions.
--Wilhelm
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692376.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by Gilles <gi...@harfang.homelinux.org>.
Hello.
It is "interesting" to see issue on such old codes...
What you propose looks sensible; the "linear" package has been known
for a long time to need an extensive redesign.
But I'm wondering about unforeseen side-effects of changing some of
those decisions without any possible feedback from those who took
them.
It might be prudent to implement the new approach in a separate
package...
On Mon, 31 Oct 2016 02:16:15 -0700 (PDT), wilbur wrote:
> OK, I built 'LUDecomposition' back to match the original Jama version
> and
> fixed a few things on the way. Performance is consistently much
> better and I
> did not notice any differences in numerical accuracy. While this
> appears to
> be the same algorithm, I have not figured out why (though I can see
> WHERE)
> the current CM implementation wastes so much time.
>
> Working myself through the code I ran into two other issues that
> should be
> fixed but will change the behavior of this class:
>
> 1) The decomposition algorithm works fine even if the input matrix A
> is
> singular. However, the current implementation exits the constructor
> as soon
> as singularity is detected and the methods getL(), getU(), and getP()
> return
> null. I propose to let the decomposition complete even for singular
> matrices
> and always return a valid decomposition. As usual, the returned
> 'DecompositionSolver' will raise an exception when solve() is invoked
> on a
> singular matrix.
>
> 2) In the current implementation, the methods getL(), getU(), and
> getP()
> return references to the SAME (cached) matrix objects in successive
> calls.
> This appears to be unjustified and bad programming practice, since
> RealMatrix objects are mutable. For some reason, though, this is
> considered
> an important feature, since it is explicitly tested for in the JUnit
> test. I
> propose to cache the corresponding primitive arrays and return a new
> matrix
> instance in every call (modified the JUnit test).
>
> Also, I see no reason to make the inner class 'Solver' *static*,
> since such
> an object cannot exist without the associated LUDecomposition itself.
> I this
> changed this to a non-static inner class. (Same strange pattern is
> used in
> QRDecomposition and probably elsewhere.)
>
> My proposed re-implementation can be found here
>
> <https://github.com/WilhelmBurger/commons-math/blob/master/src/main/java/org/apache/commons/math4/linear/LUDecomposition.java>
>
> and the associated JUnit tests here
>
> <https://github.com/WilhelmBurger/commons-math/blob/master/src/test/java/org/apache/commons/math4/linear/LUDecompositionTest.java>
>
> .
>
> TODO: The class 'FieldLUDecomposition' does the same but on a
> different
> matrix type -- needs to be reworked as well (possibly avoiding code
> duplication).
>
> Anyone please let me know in case of any objections or possible
> enhancements.
>
> Regards,
> Wilhelm
>
> ___
> PS: Being new to this list I am not sure how to properly create
> issues,
> since they are not open on GitHub.
The bug-tracking system is here:
https://issues.apache.org/jira/browse/MATH/
Please report your findings there and attach all relevant patches.
Hopefully, someone can review them.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
OK, I built 'LUDecomposition' back to match the original Jama version and
fixed a few things on the way. Performance is consistently much better and I
did not notice any differences in numerical accuracy. While this appears to
be the same algorithm, I have not figured out why (though I can see WHERE)
the current CM implementation wastes so much time.
Working myself through the code I ran into two other issues that should be
fixed but will change the behavior of this class:
1) The decomposition algorithm works fine even if the input matrix A is
singular. However, the current implementation exits the constructor as soon
as singularity is detected and the methods getL(), getU(), and getP() return
null. I propose to let the decomposition complete even for singular matrices
and always return a valid decomposition. As usual, the returned
'DecompositionSolver' will raise an exception when solve() is invoked on a
singular matrix.
2) In the current implementation, the methods getL(), getU(), and getP()
return references to the SAME (cached) matrix objects in successive calls.
This appears to be unjustified and bad programming practice, since
RealMatrix objects are mutable. For some reason, though, this is considered
an important feature, since it is explicitly tested for in the JUnit test. I
propose to cache the corresponding primitive arrays and return a new matrix
instance in every call (modified the JUnit test).
Also, I see no reason to make the inner class 'Solver' *static*, since such
an object cannot exist without the associated LUDecomposition itself. I this
changed this to a non-static inner class. (Same strange pattern is used in
QRDecomposition and probably elsewhere.)
My proposed re-implementation can be found here
<https://github.com/WilhelmBurger/commons-math/blob/master/src/main/java/org/apache/commons/math4/linear/LUDecomposition.java>
and the associated JUnit tests here
<https://github.com/WilhelmBurger/commons-math/blob/master/src/test/java/org/apache/commons/math4/linear/LUDecompositionTest.java>
.
TODO: The class 'FieldLUDecomposition' does the same but on a different
matrix type -- needs to be reworked as well (possibly avoiding code
duplication).
Anyone please let me know in case of any objections or possible
enhancements.
Regards,
Wilhelm
___
PS: Being new to this list I am not sure how to properly create issues,
since they are not open on GitHub.
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692312.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sun, 30 Oct 2016 00:40:47 -0700 (PDT), wilbur wrote:
> I am fine to submit a PR that reverts LUDecomposition to the standard
> method
> used in Jama.
Is that method better in all cases (w.r.t. performance _and_
accuracy)? [If there are trade-offs, it might be interesting
to provide both alternatives.]
Overall, the decomposition code in "LUDecomposition" code is
less than 50 lines; it would be nice to discover why the
performance is so much different...
Regards,
Gilles
>
> --Wilhelm
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Re: LU decomposition very SLOW (commons.math3.linear)
Posted by wilbur <wi...@ieee.org>.
I am fine to submit a PR that reverts LUDecomposition to the standard method
used in Jama.
--Wilhelm
--
View this message in context: http://apache-commons.680414.n4.nabble.com/Re-Math-Re-LU-decomposition-very-SLOW-commons-math3-linear-tp4692297p4692305.html
Sent from the Commons - Dev mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org