RE Looking for a faster way
- To: mathgroup at smc.vnet.net
- Subject: [mg25045] RE [mg24998] Looking for a faster way
- From: Ranko Bojanic <rbojanic at columbus.rr.com>
- Date: Sun, 3 Sep 2000 22:11:05 -0400 (EDT)
- Organization: Ohio State University
- Sender: owner-wri-mathgroup at wolfram.com
In [mg24998] looking for a faster way Otto Linsuain wrote:
> Hi to all.
> I am looking for a faster way to achieve the following:Have two lists
> with the formats:
> xlist = {x1, x2, x3, x4,...}
> flist = {f1, f2, f3, f4, ....}
> the x's and f's are just numbers.Want the matrix:
> myMatrix[[i,j]]=(fi-fj)/(xi-xj). There are probably a thousand ways
> to avoid the Indeterminate along the diagonal.Any of them is fine,
> as long as the off-diagonal part is not touched.Speed is the real
> problem.My solution so far is:
>
> myMatrix[xlist_,flist_]:=
> Outer[Subtract,flist,flist]/(Outer[Subtract, xlist,xlist] +
> IdentityMatrix[Length[xlist]])
>
> the IdentityMatrix makes the diagonal zero,rather than Indeterminate.
> This solution is not very fast because it involves 2 Outers,so that
> the speed goes roughly as 2 N^2. If I could avoid one of them
> I would have just one N^2,possibly+something-linear-in-N.
> ........
> ........
> For lists in the length range I am interested in (from 200 to 1000
> elements) the second solution is slower than the first,despite the
> fact that it uses only one Outer.If anyone can
> think of something faster than the first solution I would really
> appreciate it.
> Otto Linsuain.
>
Otto:
There is no need to work with Outer. I have tried the function
myMatrix[xlist_,flist_]:= Map[(# - flist)&, flist] /
( Map[(# - xlist)&,xlist] + IdentityMatrix[Length[xlist]])
and it works fine.
xlist = Table[Random[],500];
flist = Sin[xlist];
Using the first method I got
myMatrix[xlist,flist];//Timing
{37.9 Second,Null}
Using the second method the result was much better:
myMatrix[xlist,flist];//Timing
{2.5833 Second,Null}
(I have a Power Macintosh 7500/100 running under OS 9.04)
When I changed the number of elements in xlist to 1000,
the first method the first method could not complete the computations
complaining that there was not enough memory. The second method
gave the result {9.46667 Second,Null}
Ranko Bojanic
bojanic at math.ohio-state.edu