       Band too slow when constructing a SparseArray

• To: mathgroup at smc.vnet.net
• Subject: [mg106980] Band too slow when constructing a SparseArray
• From: "Norbert P." <bertapozar at gmail.com>
• Date: Sat, 30 Jan 2010 07:12:50 -0500 (EST)

```Hi everyone,

this has been driving me crazy for a while. I'm using Mathematica
7.0.1, Win XP. I had the same problem on 6.0.2.

I've implemented a nonlinear PDE solver that uses an implicit method,
i.e. I need to solve a system of linear equations at every step, say
~40,000. I'm surprised how fast Mathematica can be when everything is
implemented using SparseArray and packed arrays.

Now my problem: I need to construct a new matrix at each iteration
(nonlinear system). It is a sparse matrix with 5 bands. But using Band
to do this is prohibitively slow.  The matrix construction using the
simple SparseArray[Band[{1,1}]->vector,...] takes much more than the
actual LinearSolve!

I found a way how to speed this up by at least 100x. It turns out that
the construction of a diagonal matrix using SparseArray[{i_,i_}:>vector
[[i]], {n,n}] is incredibly fast (this is the only pattern that is
fast). I can't use DiagonalMatrix here since that requires a
SparseArray as an argument to produce SparseArray, slowing the process
down (unfortunate new feature in v7). Then matrix operations like
diagonal matrices using my vectors and combine them together this way.
Works nice.

My question: Why doesn't Band work at least as fast? SparseArray[Band
[{1,1}]->v] looks like it should work better then using pattern
SparseArray[{i_,i_}:>vector[[i]], {n,n}] . Is there a good reason why
I have to construct a banded matrices this way? Why isn't this
mentioned in the documentation?

A test case:
In:=
v=RandomReal[1.,1000000];
(m1=SparseArray[{i_,i_}:>v[[i]],{Length[v],Length[v]}])//Timing
Tr[m1]-Tr[v]//Timing
SparseArray[{i_,i_}->1.,{Length[v],Length[v]}]//Timing
(m2=SparseArray[Band[{1,1}]->v,{Length[v],Length[v]}])//Timing
m1==m2

Out= {0.016,SparseArray[<1000000>,{1000000,1000000}]}
Out= {0.031,-9.31323*10^-9}
Out= {0.078,SparseArray[<1000000>,{1000000,1000000}]}
Out= {12.047,SparseArray[<1000000>,{1000000,1000000}]}
Out= True

As you can see, using the pattern is 750x faster than using Band!! And
the construction of a diagonal matrix with values from a list is 3
times faster than doing the same with constants...

Best,
Norbert

```

• Prev by Date: Re: mathematica doesn't find periodic response with laplace transform
• Next by Date: Re: Prime Segment Diagram; why the codes run very slowly?
• Previous by thread: Re: Problem with ContourPlot3D
• Next by thread: Coloring a Sum