[math] Iterative linear solvers (MATH-581) again

[Sebastien Brisard <se...@m4x.org>]

Hi everyone,
well the message below did not raise much of an interest... My apology, I
forgot to quote [math] in the title.
Anyway, I have a new proposal regarding this issue. I do not know what your
view on the subject is, but I tend to think that exceptions should return
references and not deep copies of the objects that caused these exceptions to
be raised. This facilitates debugging (I guess), and also helps identify the
exact origin of the problem, without having to specialize the exception. As an
example, Conjugate Gradient requires positive definiteness of both matrix (a)
and preconditioner (m). If a NonPositiveDefiniteLinearOperatorException is
caught, then I can simply test
a == e.getOffendingLinearOperator()
or
m = e.getOffendingLinearOperator()

Now, coming to offending vectors, the issue is that these can either be
instances of RealVector, or double[]. So, what type should be returned by
getOffendingVector()?

I propose to have the exceptions return a reference to the RealVector. If the
exception was raised with a double[], then the returned RealVector will
actually be an instance of ArrayRealVector, with a reference to the initial
double[]. All this is to be clearly specified in the javadoc. Does that sound
like a viable option?

I'll attach the corresponding files to the JIRA issue, if you want to have a
more precise idea of what I'm talking about.

Thanks in advance for your comments,
Sebastien

>Good morning,
>my proposal for the implementation of linear iterative solvers (JIRA
MATH-581)
>has raised some comments from Gilles and Luc, but I think no consensus has
>been reached on one issue raised by Gilles. Before submitting a new version
of
>the corresponding classes, I'd like to make a new proposal.
>
>Here is the thing. I have defined two exceptions, namely
>  - NonSelfAdjointLinearOperatorException
>  - NonPositiveDefiniteLinearOperatorException,
>the latter being typically raised when a vector x is found, such as x'.A.x
<=
>0, where A is the linear operator under consideration.
>
>Now, the constructor of this exception takes as input A and x (which I call
>the "offending vector"). There is a method to return a reference to A (which
>is a RealLinearOperator), and a method to return a deep copy of x, the
reason
>for this is that x can either be a double[], or a RealVector.
>
>I agree with Gilles, for debugging purposes, it would probably be better to
be
>able to trace the offending vector, hence to have the exception return a
>reference to this offending vector. But this is just not possible, since
there
>is no unique type for this vector. Gilles pointed out that there is the
method
>getData() in RealVector which would do the job, but there is no requirement
in
>the contract of this method for this to be a shallow/deep copy. Is this a
>concern ? If not, then I could change the current method
>void copyOffendingVector(final double[] x)
>(where x is modified)
>into
>double[] getOffendingVector()
>but we would lose the track of the actual object which first raised the
>exception.
>
>Another option would be to have the method getOffendingVector() return an
>Object, and try to cast it to a RealVector or a double[] when catching the
>exception. Not too sure it's good practice to return Objects, though.
>
>I'm looking forward to reading your comments, and will update the sources
>accordingly.
>
>Sebastien

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

Re: [math] Iterative linear solvers (MATH-581) again

[Gilles Sadowski <gi...@harfang.homelinux.org>]

On Fri, Jul 08, 2011 at 08:44:15AM +0200, Sebastien Brisard wrote:
> Hi everyone,
> well the message below did not raise much of an interest... My apology, I
> forgot to quote [math] in the title.
> Anyway, I have a new proposal regarding this issue. I do not know what your
> view on the subject is, but I tend to think that exceptions should return
> references and not deep copies of the objects that caused these exceptions to
> be raised. This facilitates debugging (I guess), and also helps identify the
> exact origin of the problem, without having to specialize the exception. As an
> example, Conjugate Gradient requires positive definiteness of both matrix (a)
> and preconditioner (m). If a NonPositiveDefiniteLinearOperatorException is
> caught, then I can simply test
> a == e.getOffendingLinearOperator()
> or
> m = e.getOffendingLinearOperator()
> 
> Now, coming to offending vectors, the issue is that these can either be
> instances of RealVector, or double[]. So, what type should be returned by
> getOffendingVector()?
> 
> I propose to have the exceptions return a reference to the RealVector.

It looks like the best solution.

> If the
> exception was raised with a double[], then the returned RealVector will
> actually be an instance of ArrayRealVector, with a reference to the initial
> double[]. All this is to be clearly specified in the javadoc. Does that sound
> like a viable option?
> 
> I'll attach the corresponding files to the JIRA issue, if you want to have a
> more precise idea of what I'm talking about.

Regards,
Gilles

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

Re: [math] Iterative linear solvers (MATH-581) again

[Gilles Sadowski <gi...@harfang.homelinux.org>]

On Fri, Jul 08, 2011 at 12:28:23PM +0200, Sébastien Brisard wrote:
> >
> > I would go to the natural type we get when building the exception. If we may
> > build the exception from both types, then I would select RealVector. We do
> > not intend to perform large processing on elements, but we want to display
> > them and I think we do have formatting for vectors.
> >
> > best regards,
> > Luc
> 
> I actually was not thinking of speed for --as you mentioned--
> exceptional cases, but rather to ease of debugging. If several vectors
> could have caused the exception, it's easier to identify the right one
> if we have a reference rather than a deep copy (overwise all the
> components must be tested).
> 
> Speaking of speed, I do have a performance issue, which I stated this
> morning in MATH-581, but maybe it would be better to ask the question
> here. Suppose I want to implement a method operate, which computes the
> matrix-vector product. I read a long time ago that it was better to
> have a method signature like
> void operate(double[] x, double[] y)
> where x is the vector to be multiplied, and y the result. Such a
> choice avoids costly (so they said) memory allocations caused by a
> signature like
> double[] operate(double[] x)
> 
> The thing is the first option is not frequently met in Commons-Math.
> I've started to work with this option for iterative linear solvers,
> but I do not like the inconsistent feel it has with the rest of CM.
> Also, very crude monitoring on rather large linear systems (800,000 x
> 800,000)  shows that memory allocations are not even measurable... As
> I said, I read that a long time ago, and someone already mentioned on
> this forum that GC is getting pretty good those days... So is it
> really worth worrying about memory allocation?
> 
> I do not intend to do a thorough benchmarking, but I'd rather like to
> get rid of operate(double[], double[]) and keep only the most natural
> one.

+1

Gilles

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

Re: [math] Iterative linear solvers (MATH-581) again

[Luc Maisonobe <Lu...@free.fr>]

Le 08/07/2011 12:28, Sébastien Brisard a écrit :
>>
>> I would go to the natural type we get when building the exception. If we may
>> build the exception from both types, then I would select RealVector. We do
>> not intend to perform large processing on elements, but we want to display
>> them and I think we do have formatting for vectors.
>>
>> best regards,
>> Luc
>
> I actually was not thinking of speed for --as you mentioned--
> exceptional cases, but rather to ease of debugging. If several vectors
> could have caused the exception, it's easier to identify the right one
> if we have a reference rather than a deep copy (overwise all the
> components must be tested).
>
> Speaking of speed, I do have a performance issue, which I stated this
> morning in MATH-581, but maybe it would be better to ask the question
> here. Suppose I want to implement a method operate, which computes the
> matrix-vector product. I read a long time ago that it was better to
> have a method signature like
> void operate(double[] x, double[] y)
> where x is the vector to be multiplied, and y the result. Such a
> choice avoids costly (so they said) memory allocations caused by a
> signature like
> double[] operate(double[] x)

I also used to do that a long time ago, but since about 3 or 5 years, I 
changed my mind.

>
> The thing is the first option is not frequently met in Commons-Math.

It still appears for example in the ODE interfaces. State vector y and 
its derivatives yDot are allocated once and reused, but this is more an 
historic special case than mainstream.

> I've started to work with this option for iterative linear solvers,
> but I do not like the inconsistent feel it has with the rest of CM.
> Also, very crude monitoring on rather large linear systems (800,000 x
> 800,000)  shows that memory allocations are not even measurable... As

Allocation is even less measurable for large data chunks than lots of 
small ones. So what you observe is expected.

> I said, I read that a long time ago, and someone already mentioned on
> this forum that GC is getting pretty good those days... So is it
> really worth worrying about memory allocation?

It should be considered only if problems are really observed, not 
beforehand.

What is more important, especially for large data sets, is cache 
behaviour, which may be a bottleneck. In fact, about 20 years ago, 
algorithms were compared according to number of operations, then 10 
years ago dynamic allocation became a problem, now that processors are 
fast and memory is huge, cache is the problem.

>
> I do not intend to do a thorough benchmarking, but I'd rather like to
> get rid of operate(double[], double[]) and keep only the most natural
> one.

I agree with you. Maintenance of the code, readability, testing are very 
important too. We have a tendency (at least me) to set up too complex 
algorithms for too small improvements, we must make a real effort to 
build more straightforward and more robust code.

best regards,
Luc

>
> Any thoughts on this ?
> Sebastien
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-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] Iterative linear solvers (MATH-581) again

[Ted Dunning <te...@gmail.com>]

As your measurements indicate, the allocation of large objects is rarely a
speed issue.  It can be a memory fragmentation issue, but a full GC will fix
that as well.

People who are stressed about allocation of result vectors such as what you
are doing are mostly worried about the wrong thing.

2011/7/8 Sébastien Brisard <se...@m4x.org>

> The thing is the first option is not frequently met in Commons-Math.
> I've started to work with this option for iterative linear solvers,
> but I do not like the inconsistent feel it has with the rest of CM.
> Also, very crude monitoring on rather large linear systems (800,000 x
> 800,000)  shows that memory allocations are not even measurable... As
> I said, I read that a long time ago, and someone already mentioned on
> this forum that GC is getting pretty good those days... So is it
> really worth worrying about memory allocation?
>

Re: [math] Iterative linear solvers (MATH-581) again

[Sébastien Brisard <se...@m4x.org>]

>
> I would go to the natural type we get when building the exception. If we may
> build the exception from both types, then I would select RealVector. We do
> not intend to perform large processing on elements, but we want to display
> them and I think we do have formatting for vectors.
>
> best regards,
> Luc

I actually was not thinking of speed for --as you mentioned--
exceptional cases, but rather to ease of debugging. If several vectors
could have caused the exception, it's easier to identify the right one
if we have a reference rather than a deep copy (overwise all the
components must be tested).

Speaking of speed, I do have a performance issue, which I stated this
morning in MATH-581, but maybe it would be better to ask the question
here. Suppose I want to implement a method operate, which computes the
matrix-vector product. I read a long time ago that it was better to
have a method signature like
void operate(double[] x, double[] y)
where x is the vector to be multiplied, and y the result. Such a
choice avoids costly (so they said) memory allocations caused by a
signature like
double[] operate(double[] x)

The thing is the first option is not frequently met in Commons-Math.
I've started to work with this option for iterative linear solvers,
but I do not like the inconsistent feel it has with the rest of CM.
Also, very crude monitoring on rather large linear systems (800,000 x
800,000)  shows that memory allocations are not even measurable... As
I said, I read that a long time ago, and someone already mentioned on
this forum that GC is getting pretty good those days... So is it
really worth worrying about memory allocation?

I do not intend to do a thorough benchmarking, but I'd rather like to
get rid of operate(double[], double[]) and keep only the most natural
one.

Any thoughts on this ?
Sebastien

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

Re: [math] Iterative linear solvers (MATH-581) again

[Luc Maisonobe <Lu...@free.fr>]

Le 08/07/2011 08:44, Sebastien Brisard a écrit :
> Hi everyone,
> well the message below did not raise much of an interest... My apology, I
> forgot to quote [math] in the title.

Sorry, I forgot to reply in a timely fashion.

> Anyway, I have a new proposal regarding this issue. I do not know what your
> view on the subject is, but I tend to think that exceptions should return
> references and not deep copies of the objects that caused these exceptions to
> be raised. This facilitates debugging (I guess), and also helps identify the
> exact origin of the problem, without having to specialize the exception. As an

Yes, exception are targeted towards handling of ... exceptional cases, 
not heavy duty use during normal production. As such, they should not be 
over-optimized for speed.

> example, Conjugate Gradient requires positive definiteness of both matrix (a)
> and preconditioner (m). If a NonPositiveDefiniteLinearOperatorException is
> caught, then I can simply test
> a == e.getOffendingLinearOperator()
> or
> m = e.getOffendingLinearOperator()
>
> Now, coming to offending vectors, the issue is that these can either be
> instances of RealVector, or double[]. So, what type should be returned by
> getOffendingVector()?
>
> I propose to have the exceptions return a reference to the RealVector. If the
> exception was raised with a double[], then the returned RealVector will
> actually be an instance of ArrayRealVector, with a reference to the initial
> double[]. All this is to be clearly specified in the javadoc. Does that sound
> like a viable option?

I would go to the natural type we get when building the exception. If we 
may build the exception from both types, then I would select RealVector. 
We do not intend to perform large processing on elements, but we want to 
display them and I think we do have formatting for vectors.

best regards,
Luc

>
> I'll attach the corresponding files to the JIRA issue, if you want to have a
> more precise idea of what I'm talking about.
>
> Thanks in advance for your comments,
> Sebastien
>
>> Good morning,
>> my proposal for the implementation of linear iterative solvers (JIRA
> MATH-581)
>> has raised some comments from Gilles and Luc, but I think no consensus has
>> been reached on one issue raised by Gilles. Before submitting a new version
> of
>> the corresponding classes, I'd like to make a new proposal.
>>
>> Here is the thing. I have defined two exceptions, namely
>>   - NonSelfAdjointLinearOperatorException
>>   - NonPositiveDefiniteLinearOperatorException,
>> the latter being typically raised when a vector x is found, such as x'.A.x
> <=
>> 0, where A is the linear operator under consideration.
>>
>> Now, the constructor of this exception takes as input A and x (which I call
>> the "offending vector"). There is a method to return a reference to A (which
>> is a RealLinearOperator), and a method to return a deep copy of x, the
> reason
>> for this is that x can either be a double[], or a RealVector.
>>
>> I agree with Gilles, for debugging purposes, it would probably be better to
> be
>> able to trace the offending vector, hence to have the exception return a
>> reference to this offending vector. But this is just not possible, since
> there
>> is no unique type for this vector. Gilles pointed out that there is the
> method
>> getData() in RealVector which would do the job, but there is no requirement
> in
>> the contract of this method for this to be a shallow/deep copy. Is this a
>> concern ? If not, then I could change the current method
>> void copyOffendingVector(final double[] x)
>> (where x is modified)
>> into
>> double[] getOffendingVector()
>> but we would lose the track of the actual object which first raised the
>> exception.
>>
>> Another option would be to have the method getOffendingVector() return an
>> Object, and try to cast it to a RealVector or a double[] when catching the
>> exception. Not too sure it's good practice to return Objects, though.
>>
>> I'm looking forward to reading your comments, and will update the sources
>> accordingly.
>>
>> Sebastien
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>


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