commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: [math] refactoring least squares
Date Mon, 24 Feb 2014 18:16:42 GMT
On Mon, 24 Feb 2014 18:09:26 +0100, Luc Maisonobe wrote:
> Hi Evan,
>
> Le 24/02/2014 17:49, Evan Ward a écrit :
>> I've looked into improving performance further, but it seems any 
>> further
>> improvements will need big API changes for memory management.
>>
>> Currently using Gauss-Newton with Cholesky (or LU) requires 4 matrix
>> allocations _each_ evaluation. The objective function initially
>> allocates the Jacobian matrix. Then the weights are applied through
>> matrix multiplication, allocating a new matrix. Computing the normal
>> equations allocates a new matrix to hold the result, and finally the
>> decomposition allocates it's own matrix as a copy. With QR there are 
>> 3
>> matrix allocations each model function evaluation, since there is no
>> need to compute the normal equations, but the third allocation+copy 
>> is
>> larger. Some empirical sampling data I've collected with the 
>> jvisualvm
>> tool indicates that matrix allocation and copying takes 30% to 80% 
>> of
>> the execution time, depending on the dimension of the Jacobian.
>>
>> One way to improve performance would be to provide pre-allocated 
>> space
>> for the Jacobian and reuse it for each evaluation. The
>> LeastSquaresProblem interface would then be:
>>
>> void evaluate(RealVector point, RealVector resultResiduals, 
>> RealVector
>> resultJacobian);
>>
>> I'm interested in hearing your ideas on other approaches to solve 
>> this
>> issue. Or even if this is an issue worth solving.
>
> Yes, I think this issue is worth solving, especially since we are 
> going
> to ship 3.3 and need to fix as much as possible before the release, 
> thus
> avoiding future problems. Everything spotted now is worth fixing now.
>
> Your approach seems reasonable, as long as the work arrays are really
> allocated at the start of the optimization and shared only through a 
> few
> documented methods like the one you propose. This would mean we can 
> say
> in the javadoc that these area should be used only to fulfill the API
> requirements and not copied elsewhere, as they *will* be modified as 
> the
> algorithm run, and are explicitly devoted to avoid reallocation. I 
> guess
> this kind of problems is more important when lots of observations are
> performed, which correspond to very frequent use case (at least in 
> the
> fields I know about).
>
> For the record, what you propose seems similar to what is done in the
> ODE package, as the state vector and its first derivatives are also 
> kept
> in preallocated arrays which are reused throughout the integration 
> and
> are used to exchange data between the Apache Commons Math algorithm 
> and
> the user problem to be solved. So it is somehting we already do 
> elsewhere.

If I understand correctly what is being discussed, I do not agree with
this approach.

The optimization/fitting algorithms must use matrix abstractions.
If performance improvements can achieved, they must happen at the level
of the appropriate matrix implementations.


Best regards,
Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message