Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Efficient Replacement Rules to Matrix?

• To: mathgroup at smc.vnet.net
• Subject: [mg21792] Re: [mg21743] Efficient Replacement Rules to Matrix?
• From: Hartmut Wolf <hwolf at debis.com>
• Date: Thu, 27 Jan 2000 22:57:29 -0500 (EST)
• Organization: debis Systemhaus
• References: <200001260845.DAA02364@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Roger Jones schrieb:
> 
> What is the most efficient (in terms of time) method to transform a set
> of replacement rules to a matrix.  For example, I have:
> 
> matrix = ZeroMatrix[5];
> repmat = {{1, 1} -> 4., {5, 5} -> 3,{4, 4} -> 10,{2, 2} -> 2 + I 6, {3,
> 3} -> 40.};
> 
> and I transfor to a matrix thus:
> 
> matrix = ReplacePart[matrix, Sequence @@ #]) & /@ (
>       {Last[#], #[[1]]} & /@ matrix);
> 
> But for large matrices this is quite slow!  Is there a more efficient
> method?
> 
> I then will form a matrix product with this sparse matrix:
> result= matrix.avector and this is indeed my goal.
> 
> I would appreciate any ideas on this matter.
> Many thanks!
> 
> -Roger Jones
> 
> PS This comes to light in the context of using the new Mathematica
> function "SparseLinearSolve"


Dear Roger,

look at the timings

In[1]:= << LinearAlgebra`MatrixManipulation`

In[2]:=
Function[{dim},
   repmat = Table[{Random[Integer, {1, dim}], 
                   Random[Integer, {1, dim}]} -> Random[], {dim}]; 
   {Timing[matrix = ZeroMatrix[dim]; ][[1, 1]],
    Timing[Apply[(matrix[[Sequence @@ #1]] = #2) & , repmat, {1}]; ][[1,
1]],
    matrix = ZeroMatrix[dim]; 
    Timing[((matrix = ReplacePart[matrix, Sequence @@ #1]) & ) /@ 
    ({Last[#1], #1[[1]]} & ) /@ repmat; ][[1, 1]]}
] /@ {250, 500, 1000, 2000, 4000}

Out[2]=
{{0.08, 0.1, 0.321}, {0.331, 0.24, 1.132}, {1.321, 0.741, 4.626}, 
 {5.077, 2.123, 17.736}, {20.129, 7.521, 72.234}}

In[3]:= << Graphics`MultipleListPlot`
In[4]:= MultipleListPlot[Transpose[%%], PlotJoined -> True, 
  PlotLegend -> {"ZeroMatrix", "Set", "ReplacePart"}, PlotRange -> All]

The problem with your solution is that matrix must be copied too often.
The last measurement point, i.e. 72.234 is not quite fair, since my
machine (256 MB core) went into paging! Watching the Windows NT-Task
Manager, my estimate is that it should be corrected down to about ~60
for CPU usage. However, your machine might page too.

Of course I don't know what is most efficient, but here you get a factor
of eight for 4000 x 4000 matrices.

Kind regards, Hartmut

----------
P.S.: I also tried an essentially different method

Block[{xmat = {}, s}, 
  FoldList[(xmat = {xmat, 
      Table[0, {(s = (#2[[1, 1]] - 1)dim + #2[[1, 2]]) - #1 - 1}],
#2[[2]]}; s) &, 
      0, Sort[repmat]]; 
  Partition[Flatten[{xmat, Table[0, {dim^2 - s}]}], dim]]

but it's worse than yours.

• References:
  • Efficient Replacement Rules to Matrix?
    • From: Roger Jones <rmj@leland.stanford.edu>