DoubleSparseVector


1   package JSci.maths.vectors;
2   
3   import JSci.GlobalSettings;
4   import JSci.maths.MathDouble;
5   import JSci.maths.MathInteger;
6   import JSci.maths.Mapping;
7   import JSci.maths.matrices.DoubleSparseMatrix;
8   import JSci.maths.groups.AbelianGroup;
9   import JSci.maths.algebras.Module;
10  import JSci.maths.algebras.VectorSpace;
11  import JSci.maths.fields.Ring;
12  import JSci.maths.fields.Field;
13  
14  /**
15  * The DoubleSparseVector class encapsulates sparse vectors.
16  * Uses Morse-coding.
17  * @author Daniel Lemire
18  * @author Alain Beliveau
19  */
20  public final class DoubleSparseVector extends AbstractDoubleVector {
21          private double vector[];
22          /**
23          * Sparse indexing data.
24          * Contains the component positions of each element,
25          * e.g. <code>pos[n]</code> is the component position
26          * of the <code>n</code>th element
27          * (the <code>pos[n]</code>th component is stored at index <code>n</code>).
28          */
29          private int pos[];
30          /**
31          * Constructs an empty vector.
32          * @param dim the dimension of the vector.
33          */
34          public DoubleSparseVector(final int dim) {
35                  super(dim);
36                  vector=new double[0];
37                  pos=new int[0];
38          }
39          /**
40          * Constructs a vector from an array.
41          */
42          public DoubleSparseVector(double array[]) {
43                  super(array.length);
44                  int n=0;
45                  for(int i=0;i<N;i++) {
46                          if(array[i]!=0.0)
47                                  n++;
48                  }
49                  vector=new double[n];
50                  pos=new int[n];
51                  n=0;
52                  for(int i=0;i<N;i++) {
53                          if(array[i]!=0.0) {
54                                  vector[n]=array[i];
55                                  pos[n]=i;
56                                  n++;
57                          }
58                  }
59          }
60          /**
61          * Compares two vectors for equality.
62          * @param obj a double sparse vector
63          */
64      public boolean equals(Object   obj, double tol) {
65                  if(obj!=null && (obj instanceof DoubleSparseVector) && N==((DoubleSparseVector)obj).N) {
66                          DoubleSparseVector v=(DoubleSparseVector)obj;
67                          if(pos.length!=v.pos.length)
68                                  return false;
69                          double sumSqr = 0.0;
70                          for(int i=0; i<pos.length; i++) {
71                                  if(pos[i] != v.pos[i])
72                                          return false;
73                                  double delta = vector[i]-v.vector[i];
74                                  sumSqr += delta*delta;
75                          }
76                          return (sumSqr <= tol*tol);
77                  } else
78                          return false;
79          }
80          /**
81          * Returns a component of this vector.
82          * @param n index of the vector component
83          * @exception VectorDimensionException If attempting to access an invalid component.
84          */
85          public double getComponent(int n) {
86                  if(n<0 || n>=N)
87                          throw new VectorDimensionException(getInvalidComponentMsg(n));
88                  for(int k=0;k<pos.length;k++) {
89                          if(pos[k]==n)
90                                  return vector[k];
91                  }
92                  return 0.0;
93          }
94          /**
95          * Sets the value of a component of this vector.
96          * @param n index of the vector component
97          * @param x a number
98          * @exception VectorDimensionException If attempting to access an invalid component.
99          */
100         public void setComponent(int n,double x) {
101                 if(n<0 || n>=N)
102                         throw new VectorDimensionException(getInvalidComponentMsg(n));
103                 if(Math.abs(x)<=GlobalSettings.ZERO_TOL)
104                         return;
105                 for(int k=0;k<pos.length;k++) {
106                         if(n==pos[k]) {
107                                 vector[k]=x;
108                                 return;
109                         }
110                 }
111                 int newPos[]=new int[pos.length+1];
112                 double newVector[]=new double[vector.length+1];
113                 System.arraycopy(pos,0,newPos,0,pos.length);
114                 System.arraycopy(vector,0,newVector,0,pos.length);
115                 newPos[pos.length]=n;
116                 newVector[vector.length]=x;
117                 pos=newPos;
118                 vector=newVector;
119         }
120         /**
121         * Returns the l<sup>2</sup>-norm (magnitude).
122         */
123         public double norm() {
124                 return Math.sqrt(sumSquares());
125         }
126         /**
127         * Returns the sum of the squares of the components.
128         */
129         public double sumSquares() {
130                 double norm=0.0;
131         for(int k=0;k<pos.length;k++)
132             norm+=vector[k]*vector[k];
133         return norm;
134         }
135         /**
136         * Returns the mass.
137         */
138         public double mass() {
139                 double mass=0.0;
140         for(int k=0;k<pos.length;k++)
141             mass+=vector[k];
142         return mass;
143         }
144 
145 //============
146 // OPERATIONS
147 //============
148 
149         /**
150         * Returns the negative of this vector.
151         */
152         public AbelianGroup.Member negate() {
153                 final DoubleSparseVector ans = new DoubleSparseVector(N);
154                 ans.vector = new double[vector.length];
155                 ans.pos = new int[pos.length];
156                 System.arraycopy(pos, 0, ans.pos, 0, pos.length);
157                 for(int i=0; i<pos.length; i++)
158                         ans.vector[i] =- vector[i];
159                 return ans;
160         }
161 
162 // ADDITION
163 
164         /**
165         * Returns the addition of this vector and another.
166         */
167         public AbelianGroup.Member add(final AbelianGroup.Member v) {
168                 if(v instanceof AbstractDoubleVector)
169                         return add((AbstractDoubleVector)v);
170                 else
171                         throw new IllegalArgumentException  ("Member class not recognised by this method.");
172         }
173         /**
174         * Returns the addition of this vector and another.
175         * @param v a double vector
176         * @exception VectorDimensionException If the vectors are different sizes.
177         */
178         public AbstractDoubleVector add(final AbstractDoubleVector v) {
179                 if(v instanceof DoubleSparseVector)
180                         return add((DoubleSparseVector)v);
181                 else if(v instanceof DoubleVector)
182                         return add((DoubleVector)v);
183                 else {
184                         if(N!=v.N)
185                                 throw new VectorDimensionException("Vectors are different sizes.");
186                         double array[]=new double[N];
187                         array[0]=v.getComponent(0);
188                         for(int i=1;i<N;i++)
189                                 array[i]=v.getComponent(i);
190                         for(int i=0;i<pos.length;i++)
191                                 array[pos[i]]+=vector[i];
192                         return new DoubleVector(array);
193                 }
194         }
195         public DoubleVector add(final DoubleVector v) {
196                 if(N!=v.N)
197                         throw new VectorDimensionException("Vectors are different sizes.");
198                 double array[]=new double[N];
199                 System.arraycopy(v.vector,0,array,0,N);
200                 for(int i=0;i<pos.length;i++)
201                         array[pos[i]]+=vector[i];
202                 return new DoubleVector(array);
203         }
204         /**
205         * Returns the addition of this vector and another.
206         * @param v a double sparse vector
207         * @exception VectorDimensionException If the vectors are different sizes.
208         */
209         public DoubleSparseVector add(final DoubleSparseVector v) {
210                 if(N!=v.N)
211                         throw new VectorDimensionException("Vectors are different sizes.");
212                 double array[]=new double[N];
213                 for(int i=0;i<pos.length;i++)
214                         array[pos[i]]=vector[i]+v.getComponent(pos[i]);
215                 for(int m,i=0;i<v.pos.length;i++) {
216                         m=v.pos[i];
217                         array[m]=getComponent(m)+v.vector[i];
218                 }
219                 return new DoubleSparseVector(array);
220         }
221 
222 // SUBTRACTION
223 
224         /**
225         * Returns the subtraction of this vector by another.
226         */
227         public AbelianGroup.Member subtract(final AbelianGroup.Member v) {
228                 if(v instanceof AbstractDoubleVector)
229                         return subtract((AbstractDoubleVector)v);
230                 else
231                         throw new IllegalArgumentException  ("Member class not recognised by this method.");
232         }
233         /**
234         * Returns the subtraction of this vector by another.
235         * @param v a double vector
236         * @exception VectorDimensionException If the vectors are different sizes.
237         */
238         public AbstractDoubleVector subtract(final AbstractDoubleVector v) {
239                 if(v instanceof DoubleSparseVector)
240                         return subtract((DoubleSparseVector)v);
241                 else if(v instanceof DoubleVector)
242                         return subtract((DoubleVector)v);
243                 else {
244                         if(N!=v.N)
245                                 throw new VectorDimensionException("Vectors are different sizes.");
246                         double array[]=new double[N];
247                         array[0]=-v.getComponent(0);
248                         for(int i=1;i<N;i++)
249                                 array[i]=-v.getComponent(i);
250                         for(int i=0;i<pos.length;i++)
251                                 array[pos[i]]+=vector[i];
252                         return new DoubleVector(array);
253                 }
254         }
255         public DoubleVector subtract(final DoubleVector v) {
256                 if(N!=v.N)
257                         throw new VectorDimensionException("Vectors are different sizes.");
258                 double array[]=new double[N];
259                 array[0]=-v.vector[0];
260                 for(int i=1;i<N;i++)
261                         array[i]=-v.vector[i];
262                 for(int i=0;i<pos.length;i++)
263                         array[pos[i]]+=vector[i];
264                 return new DoubleVector(array);
265         }
266         /**
267         * Returns the subtraction of this vector by another.
268         * @param v a double sparse vector
269         * @exception VectorDimensionException If the vectors are different sizes.
270         */
271         public DoubleSparseVector subtract(final DoubleSparseVector v) {
272                 if(N!=v.N)
273                         throw new VectorDimensionException("Vectors are different sizes.");
274                 double array[]=new double[N];
275                 for(int i=0;i<pos.length;i++)
276                         array[pos[i]]=vector[i]-v.getComponent(pos[i]);
277                 for(int m,i=0;i<v.pos.length;i++) {
278                         m=v.pos[i];
279                         array[m]=getComponent(m)-v.vector[i];
280                 }
281                 return new DoubleSparseVector(array);
282         }
283 
284 // SCALAR MULTIPLICATION
285 
286         /**
287         * Returns the multiplication of this vector by a scalar.
288         */
289         public Module.Member scalarMultiply(Ring.Member x) {
290                 if(x instanceof MathDouble)
291                         return scalarMultiply(((MathDouble)x).value());
292                 else if(x instanceof MathInteger)
293                         return scalarMultiply(((MathInteger)x).value());
294                 else
295                         throw new IllegalArgumentException  ("Member class not recognised by this method.");
296         }
297         /**
298         * Returns the multiplication of this vector by a scalar.
299         * @param x a double
300         */
301         public AbstractDoubleVector scalarMultiply(final double x) {
302                 final DoubleSparseVector ans=new DoubleSparseVector(N);
303                 ans.vector=new double[vector.length];
304                 ans.pos=new int[pos.length];
305                 System.arraycopy(pos,0,ans.pos,0,pos.length);
306                 for(int i=0;i<pos.length;i++)
307                         ans.vector[i]=x*vector[i];
308                 return ans;
309         }
310 
311 // SCALAR DIVISION
312 
313         /**
314         * Returns the division of this vector by a scalar.
315         */
316         public VectorSpace.Member scalarDivide(Field.Member x) {
317                 if(x instanceof MathDouble)
318                         return scalarDivide(((MathDouble)x).value());
319                 else
320                         throw new IllegalArgumentException  ("Member class not recognised by this method.");
321         }
322         /**
323         * Returns the division of this vector by a scalar.
324         * @param x a double
325         * @exception ArithmeticException If divide by zero.
326         */
327         public AbstractDoubleVector scalarDivide(final double x) {
328                 final DoubleSparseVector ans=new DoubleSparseVector(N);
329                 ans.vector=new double[vector.length];
330                 ans.pos=new int[pos.length];
331                 System.arraycopy(pos,0,ans.pos,0,pos.length);
332                 for(int i=0;i<pos.length;i++)
333                         ans.vector[i]=vector[i]/x;
334                 return ans;
335         }
336 
337 // SCALAR PRODUCT
338 
339         /**
340         * Returns the scalar product of this vector and another.
341         * @param v a double vector
342         * @exception VectorDimensionException If the vectors are different sizes.
343         */
344         public double scalarProduct(final AbstractDoubleVector v) {
345                 if(v instanceof DoubleSparseVector)
346                         return scalarProduct((DoubleSparseVector)v);
347                 else if(v instanceof DoubleVector)
348                         return scalarProduct((DoubleVector)v);
349                 else {
350                         if(N!=v.N)
351                                 throw new VectorDimensionException("Vectors are different sizes.");
352                         double ps=0.0;
353                         for(int i=0;i<pos.length;i++)
354                                 ps+=vector[i]*v.getComponent(pos[i]);
355                         return ps;
356                 }
357         }
358         public double scalarProduct(final DoubleVector v) {
359                 if(N!=v.N)
360                         throw new VectorDimensionException("Vectors are different sizes.");
361                 double ps=0.0;
362                 for(int i=0;i<pos.length;i++)
363                         ps+=vector[i]*v.vector[pos[i]];
364                 return ps;
365         }
366         /**
367         * Returns the scalar product of this vector and another.
368         * @param v a double sparse vector
369         * @exception VectorDimensionException If the vectors are different sizes.
370         */
371         public double scalarProduct(final DoubleSparseVector v) {
372                 if(N!=v.N)
373                         throw new VectorDimensionException("Vectors are different sizes.");
374                 double ps=0.0;
375                 if(pos.length<=v.pos.length) {
376                         for(int i=0;i<pos.length;i++)
377                                 ps+=vector[i]*v.getComponent(pos[i]);
378                 } else {
379                         for(int i=0;i<v.pos.length;i++)
380                                 ps+=getComponent(v.pos[i])*v.vector[i];
381                 }
382                 return ps;
383         }
384 
385 // TENSOR PRODUCT
386 
387         /**
388         * Returns the tensor product of this vector and another.
389         */
390         public DoubleSparseMatrix tensorProduct(final DoubleSparseVector v) {
391                 DoubleSparseMatrix ans=new DoubleSparseMatrix(N,v.N);
392                 for(int j,i=0;i<pos.length;i++) {
393                         for(j=0;j<v.pos.length;j++)
394                                 ans.setElement(pos[i],v.pos[j],vector[i]*v.vector[j]);
395                 }
396                 return ans;
397         }
398 
399 // MAP COMPONENTS
400 
401         /**
402         * Applies a function on all the vector components.
403         * @param f a user-defined function
404         * @return a double sparse vector
405         */
406         public AbstractDoubleVector mapComponents(final Mapping f) {
407         double zeroValue = f.map(0.0);
408         if(Math.abs(zeroValue) <= GlobalSettings.ZERO_TOL)
409             return sparseMap(f);
410         else
411             return generalMap(f, zeroValue);
412     }
413     private AbstractDoubleVector sparseMap(Mapping f) {
414                 final DoubleSparseVector ans=new DoubleSparseVector(N);
415                 ans.vector=new double[vector.length];
416                 ans.pos=new int[pos.length];
417                 System.arraycopy(pos,0,ans.pos,0,pos.length);
418                 for(int i=0;i<pos.length;i++)
419                         ans.vector[i]=f.map(vector[i]);
420                 return ans;
421         }
422     private AbstractDoubleVector generalMap(Mapping f, double zeroValue) {
423         double[] array = new double[N];
424         for(int i=0; i<N; i++)
425             array[i] = zeroValue;
426                 for(int i=0;i<pos.length;i++)
427                         array[i] = f.map(vector[pos[i]]);
428                 return new DoubleVector(array);
429         }
430 }
431
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags