[math] Transposable linear operators

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

Hi,
I'm in the middle of porting LSQR (iterative solver for unsymmetric
systems) to Commons-Math. I need to be able to define a "transposable"
real linear operator. In other words, on top of
RealVector RealLinearOperator.operate(RealVector),
I also need a method which would read
RealVector RealLinearOperator.operateTranspose(RealVector).

My problem is: how to do that?
1. Extend RealLinearOperator? That would allow for compile time
checks. The problem is I've already defined
InvertibleRealLinearOperator. So how about operators which are both
invertible and transposable?
2. Create an interface, say Transposable? But then, no compile time
check can be performed in
LSQR.RealVector solve(RealLinearOperator a, RealVector b)
(defined in AbstractIterativeLinearSolver). The only thing I can do is
test whether the specified operator implements the interface
Transposable.
3. Add the method operateTranspose to RealLinearOperator, and allow
for UnsupportedOperationException. I could then add a method
boolean isTransposable() to RealLinearOperator. Again, no compile-time
check is possible.

Do you have any thoughts?
Sébastien


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

Re: [math] Transposable linear operators

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

>
> The shorter name is fine.
>
isTransposable() it is, then!

>
> Operate is a bit funky.  A more traditional verb would be be apply()
>
Agreed. But this verb has been around for quite a time in the matrix
context, so I just kept it for RealLinearOperator.

Thanks for your interest in this issue,
Sébastien


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

Re: [math] Transposable linear operators

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

The shorter name is fine.

Operate is a bit funky.  A more traditional verb would be be apply()


2012/1/12 Sébastien Brisard <se...@m4x.org>

> Last question (***to native english speakers***): I'm not sure
> isTransposable() really means what I would like it to mean. What do
> you think of
> boolean isTranspositionSupported()?
>
> Likewise, is this name OK
> RealVector operateTranspose(RealVector)
> considering that application of the real linear operator a is called
> RealVector operate(RealVector).
>

Re: [math] Transposable linear operators

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

Hi,

>
>> That's true. So are you suggesting I should write three specialized classes
>> InvertibleRealLinearOperator,
>> TransposableRealLinearOperator,
>> InvertibleAndTransposableRealLinearOperator?
>
> not really, I think such a structuring would create more confusion and
> problems in the long run than make up for the subtle differences that it
> may model right now.
>
I agree. In fact, I'm now toying with the idea of removing
InvertibleRealLinearOperator. I initially introduced this abstract
class to handle preconditioners. In fact, if m is the preconditioner,
instead of passing m to the solver (and calling m.solve(y)), I could
just as well pass mInv = m^(-1) (and call mInv.operate(y)).

>
> Together with the comment from Ted, I think this is the best way to go.
> The isTransposable method may not be needed after all, I would be happy
> with a checked exception in case someone uses operateTranspose and it is
> not supported by the operator.
>
Like Ted, I like UnsupportedOperationException, and do not really like
catching unchecked exceptions. I hope you do not dislike the
isTransposable() option too much?

Last question (***to native english speakers***): I'm not sure
isTransposable() really means what I would like it to mean. What do
you think of
boolean isTranspositionSupported()?

Likewise, is this name OK
RealVector operateTranspose(RealVector)
considering that application of the real linear operator a is called
RealVector operate(RealVector).

Thanks for your help,
Sébastien
>
> Thomas
>


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

Re: [math] Transposable linear operators

[Thomas Neidhart <th...@gmail.com>]

On 01/12/2012 12:28 PM, Sébastien Brisard wrote:
> Hi Thomas,

[snip]

> I agree with you that any linear operator is "transposable" (don't
> even know whether this word makes sense in english). However,
> RealLinearOperator have been implemented for operators which are *not*
> known in closed-form. In other words, I do not know how to access
> efficiently the (i, j) coefficient, but I *do* know how to compute
> efficiently A.x. There might be some cases where computing A'.x would
> still be difficult. I do not have an example here, but that's the
> reason why initially
> RealVector operateTranspose(RealVector)
> was not put in the RealLinearOperator abstract class.

ok, now I understand the purpose of the operator much better.

>> @Alt1: you ask about operators which are both invertible and
>> transposable, but the two properties do not collide imho, at least as
>> long as you do not want to calculate something like y = A^T^-1 x
>>
> That's true. So are you suggesting I should write three specialized classes
> InvertibleRealLinearOperator,
> TransposableRealLinearOperator,
> InvertibleAndTransposableRealLinearOperator?

not really, I think such a structuring would create more confusion and
problems in the long run than make up for the subtle differences that it
may model right now.

>> And in that case, wouldn't it be better to create a RealLinearOperator
>> object with A^T as parameter?
>>
> Not sure I really follow, but I already thought of passing *two*
> RealLinearOperators to the LSQR solver, which requires A and A^T.

that's pretty much what I was thinking about ;-)

> I've actually started playing around with this option. Added
> RealVector operateTranspose(RealVector)
> to the RealLinearOperator abstract class. This method would be defined
> as "optional" in the Javadoc, with the option to throw an
> UnsupportedOperationException. I also thought about
> boolean isTransposable()
> to check at execution time that operateTranspose() has indeed been
> implemented. Not sure this method is absolutely necessary, though.

Together with the comment from Ted, I think this is the best way to go.
The isTransposable method may not be needed after all, I would be happy
with a checked exception in case someone uses operateTranspose and it is
not supported by the operator.

Thomas

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

Re: [math] Transposable linear operators

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

Yeah... but I am a fan of the UnsupportedOperationException so I think it
should be OK to have something like that in the interface and just throw up
if it is called.

2012/1/12 Sébastien Brisard <se...@m4x.org>

> 2012/1/12 Ted Dunning <te...@gmail.com>:
> > One such example is a text retrieval engine.  A x is easy since that is
> > what the engine does.  A' y is very expensive.
>
> Thanks for this example! So you *do* agree that implementing
> operateTranspose() should be optional, don't you?
>

Re: [math] Transposable linear operators

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

2012/1/12 Ted Dunning <te...@gmail.com>:
> One such example is a text retrieval engine.  A x is easy since that is
> what the engine does.  A' y is very expensive.
>
> 2012/1/12 Sébastien Brisard <se...@m4x.org>
>
>> In other words, I do not know how to access
>> efficiently the (i, j) coefficient, but I *do* know how to compute
>> efficiently A.x. There might be some cases where computing A'.x would
>> still be difficult. I do not have an example here, but that's the
>> reason why initially
>> RealVector operateTranspose(RealVector)
>> was not put in the RealLinearOperator abstract class.
>>

Thanks for this example! So you *do* agree that implementing
operateTranspose() should be optional, don't you?
Sébastien


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

Re: [math] Transposable linear operators

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

One such example is a text retrieval engine.  A x is easy since that is
what the engine does.  A' y is very expensive.

2012/1/12 Sébastien Brisard <se...@m4x.org>

> In other words, I do not know how to access
> efficiently the (i, j) coefficient, but I *do* know how to compute
> efficiently A.x. There might be some cases where computing A'.x would
> still be difficult. I do not have an example here, but that's the
> reason why initially
> RealVector operateTranspose(RealVector)
> was not put in the RealLinearOperator abstract class.
>

Re: [math] Transposable linear operators

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

Hi Thomas,
and thanks for digging into that!

>
> looking at the rationale behind RealLinearOperator I understand this
> class is used to calculate either:
>
>  y = A x
>  y = A^T x
>
Not exactly. For the time being, RealLinearOperator only provides the method
RealVector operate(RealVector), which performs y = A.x.

I agree with you that any linear operator is "transposable" (don't
even know whether this word makes sense in english). However,
RealLinearOperator have been implemented for operators which are *not*
known in closed-form. In other words, I do not know how to access
efficiently the (i, j) coefficient, but I *do* know how to compute
efficiently A.x. There might be some cases where computing A'.x would
still be difficult. I do not have an example here, but that's the
reason why initially
RealVector operateTranspose(RealVector)
was not put in the RealLinearOperator abstract class.

>
> The specialized class InvertibleRealLinearOperator further allows for the calculation of:
>
>  y = A^-1 x
>
right.

>
> @Alt1: you ask about operators which are both invertible and
> transposable, but the two properties do not collide imho, at least as
> long as you do not want to calculate something like y = A^T^-1 x
>
That's true. So are you suggesting I should write three specialized classes
InvertibleRealLinearOperator,
TransposableRealLinearOperator,
InvertibleAndTransposableRealLinearOperator?

>
> And in that case, wouldn't it be better to create a RealLinearOperator
> object with A^T as parameter?
>
Not sure I really follow, but I already thought of passing *two*
RealLinearOperators to the LSQR solver, which requires A and A^T.
However, LSQR would be out of the IterativeLinearSolver hierarchy in
that case, since the typical signature in this hierarchy is
RealVector solve(RealLinearOperator, RealVector),
and LSQR would require
RealVector solve(RealLinearOperator, RealLinearOperator, RealVector)

>
> @Alt2: if the solve method relies on an operator to provide
> operateTranspose than it should be checked on compile time imho.
>
Agreed. I do not like the "tagging interface option".

>
> Assuming that any matrix A should be transposable, I would opt for
> alternative 3 and provide the operateTranspose method. Do you have a
> case where an operator would not be transposable?
>
> Thomas
>
I've actually started playing around with this option. Added
RealVector operateTranspose(RealVector)
to the RealLinearOperator abstract class. This method would be defined
as "optional" in the Javadoc, with the option to throw an
UnsupportedOperationException. I also thought about
boolean isTransposable()
to check at execution time that operateTranspose() has indeed been
implemented. Not sure this method is absolutely necessary, though.

Would be glad to read your thoughts!
Sébastien


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

Re: [math] Transposable linear operators

[Thomas Neidhart <th...@gmail.com>]

On 01/11/2012 08:21 PM, Sébastien Brisard wrote:
> Hi,

Hi Sébastien,

> My problem is: how to do that?
> 1. Extend RealLinearOperator? That would allow for compile time
> checks. The problem is I've already defined
> InvertibleRealLinearOperator. So how about operators which are both
> invertible and transposable?
> 2. Create an interface, say Transposable? But then, no compile time
> check can be performed in
> LSQR.RealVector solve(RealLinearOperator a, RealVector b)
> (defined in AbstractIterativeLinearSolver). The only thing I can do is
> test whether the specified operator implements the interface
> Transposable.
> 3. Add the method operateTranspose to RealLinearOperator, and allow
> for UnsupportedOperationException. I could then add a method
> boolean isTransposable() to RealLinearOperator. Again, no compile-time
> check is possible.
> 
> Do you have any thoughts?

looking at the rationale behind RealLinearOperator I understand this
class is used to calculate either:

 y = A x
 y = A^T x

The specialized class InvertibleRealLinearOperator further allows for
the calculation of:

 y = A^-1 x

@Alt1: you ask about operators which are both invertible and
transposable, but the two properties do not collide imho, at least as
long as you do not want to calculate something like y = A^T^-1 x

And in that case, wouldn't it be better to create a RealLinearOperator
object with A^T as parameter?

@Alt2: if the solve method relies on an operator to provide
operateTranspose than it should be checked on compile time imho.

Assuming that any matrix A should be transposable, I would opt for
alternative 3 and provide the operateTranspose method. Do you have a
case where an operator would not be transposable?

Thomas

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