Prev: Ball choosing
Next: /J!| MS_5970 Single data array, variable X spacing Abundance METHOD.M
From: Pollux on 7 Jun 2010 12:33
Hi -

I have a non-symmetric 0/1 sparse matrix with uniform distribution of
the non-zeros. I want to find a permutation of the columns that will
result in a sparse matrix with the minimum distance between first and
last non-zero on each row. (the hope is to implement a spmv algorithm
that will take advantage of "semi-dense" blocks for speed, if there are
enough semi-dense blocks, and if their density of non-zeros is high enough)

Is there a known algorithm for that problem?

Thanks!

Pollux

--- news://freenews.netfront.net/ - complaints: news(a)netfront.net ---
From: Nicolas Bonneel on 7 Jun 2010 15:55
Pollux wrote:
> Hi -
>
> I have a non-symmetric 0/1 sparse matrix with uniform distribution of
> the non-zeros. I want to find a permutation of the columns that will
> result in a sparse matrix with the minimum distance between first and
> last non-zero on each row. (the hope is to implement a spmv algorithm
> that will take advantage of "semi-dense" blocks for speed, if there are
> enough semi-dense blocks, and if their density of non-zeros is high enough)
>
> Is there a known algorithm for that problem?

I would say a Cuthill MacKee algorithm ? It allows to minimize the
profile of the matrix.

Cheers

--
Nicolas Bonneel
http://cs.ubc.ca/~nbonneel/
From: Pol Lux on 7 Jun 2010 16:26
On Jun 7, 12:55 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote:
> Pollux wrote:
> > Hi -
>
> > I have a non-symmetric 0/1 sparse matrix with uniform distribution of
> > the non-zeros. I want to find a permutation of the columns that will
> > result in a sparse matrix with the minimum distance between first and
> > last non-zero on each row. (the hope is to implement a spmv algorithm
> > that will take advantage of "semi-dense" blocks for speed, if there are
> > enough semi-dense blocks, and if their density of non-zeros is high enough)
>
> > Is there a known algorithm for that problem?
>
> I would say a Cuthill MacKee algorithm ? It allows to minimize the
> profile of the matrix.
>
> Cheers
>
> --
> Nicolas Bonneelhttp://cs.ubc.ca/~nbonneel/

Hmmm.... I am aware of this algorithm, but it seems to be for
symmetric matrices only. Is it worth giving it a shot on a non-
symmetric matrix?

Pollux
From: Nicolas Bonneel on 7 Jun 2010 18:11
Pol Lux wrote:
> On Jun 7, 12:55 pm, Nicolas Bonneel <nbonn...(a)cs.ubc.ca> wrote:
>> Pollux wrote:
>>> Hi -
>>> I have a non-symmetric 0/1 sparse matrix with uniform distribution of
>>> the non-zeros. I want to find a permutation of the columns that will
>>> result in a sparse matrix with the minimum distance between first and
>>> last non-zero on each row. (the hope is to implement a spmv algorithm
>>> that will take advantage of "semi-dense" blocks for speed, if there are
>>> enough semi-dense blocks, and if their density of non-zeros is high enough)
>>> Is there a known algorithm for that problem?
>> I would say a Cuthill MacKee algorithm ? It allows to minimize the
>> profile of the matrix.
>
> Hmmm.... I am aware of this algorithm, but it seems to be for
> symmetric matrices only. Is it worth giving it a shot on a non-
> symmetric matrix?

Hi,
indeed sorry, I read too quickly.
The package "Metis" has a reordering routine for non symmetric matrices.
I think the geometry library CGAL also has some reodering routines but I
don't know if it's for symmetric matrices only or not.

Cheers
From: Han de Bruijn on 9 Jun 2010 04:45
On Jun 7, 6:33 pm, Pollux <po....(a)gmail.com> wrote:
> Hi -
>
> I have a non-symmetric 0/1 sparse matrix with uniform distribution of
> the non-zeros. I want to find a permutation of the columns that will
> result in a sparse matrix with the minimum distance between first and
> last non-zero on each row. (the hope is to implement a spmv algorithm
> that will take advantage of "semi-dense" blocks for speed, if there are
> enough semi-dense blocks, and if their density of non-zeros is high enough)
>
> Is there a known algorithm for that problem?
>
> Thanks!
>
> Pollux
>
> --- news://freenews.netfront.net/ - complaints: n...(a)netfront.net ---

Depends on what you are going to do with it. Solve a system of linear
equations and that's it? There do exist efficient _iterative_ solvers
as well ..

Han de Bruijn
 |  Next  |  Last
Pages: 1 2 3
Prev: Ball choosing
Next: /J!| MS_5970 Single data array, variable X spacing Abundance METHOD.M