Re: diagonal & permutation matrices

[Jaroslav Hajek]

On Tue, Nov 18, 2008 at 11:08 AM, Schirmacher, Rolf
<address@hidden> wrote:
>
>
>> -----Original Message-----
>> From: Jaroslav Hajek [mailto:address@hidden
>> Sent: Monday, November 17, 2008 12:18 PM
>> To: address@hidden
>> Cc: octave maintainers mailing list
>> Subject: Re: diagonal & permutation matrices
>>
>>
>> On Sun, Nov 16, 2008 at 11:34 PM, David Bateman
>> <address@hidden> wrote:
>> > Jaroslav Hajek wrote:
>> >>
>> >> On Sun, Nov 16, 2008 at 3:53 PM, David Bateman
>> <address@hidden>
>> >> wrote:
>> >>>
>> >>> Isn't this why Matlab added the 'vector' option to
>> functions like QR?
>> >>
>> >> Yes, apparently. That was the "quick and lazy" solution.
>> >>
>> >>> Then
>> >>> you replace the matrix multiplication with a matrix index
>> operation. If
>> >>> you
>> >>> prefer to keep the matrix multiply syntax, then why not
>> just make P a
>> >>> sparse
>> >>> matrix, whose matrix multiplication should be relatively fast.
>> >>
>> >> Well, it will be still slower than indexing, though at least O(N^2)
>> >> and not O(N^3).
>> >> The inconvenience is that instead of the natural syntax `[l,u,p] =
>> >> lu(a)', you need to do [l,u,p] = lu(a,"vector"); p =
>> speye(n)(p,:)`,
>> >> i.e. the default, well readable syntax is useless if you
>> don't ignore
>> >> performance.
>> >> IMHO, functions like diag, eye, and the 3rd output args of
>> lu and qr
>> >> should have always returned sparse matrices (because diagonal and
>> >> permutation matrices *are* quite sparse). It's another place where
>> >> Matlab compatibility is a pain in the ass.
>> >> I always disliked the fact that expressions like diag(x)*y are, in
>> >> fact, to be avoided in library functions. Using
>> spdiag(x)*y is almost
>> >> always much better.
>> >
>> > Sigh.... Well, its another argument of where we draw the
>> line with matlab
>> > compatibility.. We need to take care that any changes you
>> make don't have
>> > unexpected consequences for compatibility.
>> >
>> > Cheers
>> > David
>> >
>>
>> Oh, no no. Though I think my arguments are good, I'm going to put this
>> off unless more people vote for it. After all, it's just a
>> performance/cosmetic feature.
>> I guess I can just get used to writing "spdiag(D) * A" instead of
>> "diag(D) * A" and to always use lu and qr with the "vector" argument,
>> although it's ugly.
>
> Jaroslav,
>
> if my understanding is right, the "m" language is kept compatible and it is
> just our internal stuff (i.e. additional types) and algorithms which will
> result in better performance. So, octave might end up faster than the other
> brand even without JIT compiler, at least for some calculations /
> benchmarks.
>
> We will even get better performance for all that many people / cases, where
> nobody want to think (or does not know...) about the "ugly" language you
> mention - probably 99 % of all users/cases.
>

I 100% agree. The diag(D) * A expression is idiomatic. It is used a
lot throughout Matlab help,
while being mostly avoided in m-files (replaced by repmat (D, 1, n) .*
A or something), though not always.
As for permutation matrices, you can find a lot m-files not using the
"vector" argument and working in some way with the permutation matrix.
This agrees with my point - if the default, readable syntax is broken
(in terms of performance), providing a fast alternative is a much
worse solution than making the default syntax fast, because people
that do not keep performance tricks in mind all the time (and that's a
good thing) will tend to use the default syntax anyway.


> What might come up as an issue is explicit type checking in matlab (and old
> octave) code that results in different / new types. How would the new types
> be "visable" to a user through "m" syntax? Could we make it unnoticable here
> as well?
>

My point only was that if Octave knows that A is diagonal or
permutation of identity, it may be better to print this info for an
user inspecting the variable. Similarly, when Octave saves the
variable in its native format, it may be better to remember the
"diagonality" information (and only store the diagonal) than to forget
it.
As has been already pointed out, Octave's native "text" format is
incompatible with Matlab anyway.
I think that printing out the specialness but converting on save is a
reasonable compromise.

> Please do not put it off but make it available as a "simple" solution for
> arbitrary users!
>
> Just my 2 ct.
>
> Rolf
>

thanks for your opinion. I hope to finish this patch soon, so that
working diagonal and permutation matrices will suffer no performance
penalty already in 3.2.0.

regards

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz