Re: X'*v in octave

[Rik]

On 05/22/2015 09:00 AM, address@hidden wrote:

Subject:

Re: X'*v in octave

From:

Jordi Gutiérrez Hermoso <address@hidden>

Date:

05/22/2015 07:11 AM

To:

Chih-Jen Lin <address@hidden>

CC:

address@hidden, address@hidden, address@hidden

List-Post:

<mailto:address@hidden>

Content-Transfer-Encoding:

7bit

Precedence:

list

MIME-Version:

1.0

References:

<address@hidden>

In-Reply-To:

<address@hidden>

Message-ID:

<address@hidden>

Content-Type:

text/plain; charset="UTF-8"

Message:

1

On Fri, 2015-05-22 at 05:05 +0800, Chih-Jen Lin wrote:

> Recently in an experiment I found that for sparse X'*v octave seems
> to do X' first and then conduct the matrix vector product. This is
> time consuming as this operation is simple a linear combination of
> X's columns and X in Octave is stored in compressed column format.

I may be completely mistaken here, but I think that Octave is already
doing what you suggest. If you attempt the following,

    x = sprand(1e5,1e5,0.0001);
    y = rand(1e4,1);

then of the possible operations of interest,

    tic; x*y; toc
    tic; y'*x; toc
    tic; x'*y; toc

the third one is the fastest. Are you seeing one of the two others as
being faster?

- Jordi G. H.

Results from testing with the Mercurial ID 561af1ab6099 on the development branch:

octave:11>     tic; x*y; toc
Elapsed time is 0.0312591 seconds.
octave:12>     tic; y'*x; toc
Elapsed time is 0.022948 seconds.
octave:13>     tic; x'*y; toc
Elapsed time is 0.0130401 seconds.

It appears that Jordi is right that this case is already significantly faster than straightforward multiplication of x*y.

--Rik