001: package JSci.maths.vectors;
002:
003: import JSci.GlobalSettings;
004: import JSci.maths.MathDouble;
005: import JSci.maths.MathInteger;
006: import JSci.maths.Mapping;
007: import JSci.maths.matrices.DoubleSparseMatrix;
008: import JSci.maths.groups.AbelianGroup;
009: import JSci.maths.algebras.Module;
010: import JSci.maths.algebras.VectorSpace;
011: import JSci.maths.fields.Ring;
012: import JSci.maths.fields.Field;
013:
014: /**
015: * The DoubleSparseVector class encapsulates sparse vectors.
016: * Uses Morse-coding.
017: * @author Daniel Lemire
018: * @author Alain Beliveau
019: */
020: public final class DoubleSparseVector extends AbstractDoubleVector {
021: private double vector[];
022: /**
023: * Sparse indexing data.
024: * Contains the component positions of each element,
025: * e.g. <code>pos[n]</code> is the component position
026: * of the <code>n</code>th element
027: * (the <code>pos[n]</code>th component is stored at index <code>n</code>).
028: */
029: private int pos[];
030:
031: /**
032: * Constructs an empty vector.
033: * @param dim the dimension of the vector.
034: */
035: public DoubleSparseVector(final int dim) {
036: super (dim);
037: vector = new double[0];
038: pos = new int[0];
039: }
040:
041: /**
042: * Constructs a vector from an array.
043: */
044: public DoubleSparseVector(double array[]) {
045: super (array.length);
046: int n = 0;
047: for (int i = 0; i < N; i++) {
048: if (array[i] != 0.0)
049: n++;
050: }
051: vector = new double[n];
052: pos = new int[n];
053: n = 0;
054: for (int i = 0; i < N; i++) {
055: if (array[i] != 0.0) {
056: vector[n] = array[i];
057: pos[n] = i;
058: n++;
059: }
060: }
061: }
062:
063: /**
064: * Compares two vectors for equality.
065: * @param obj a double sparse vector
066: */
067: public boolean equals(Object obj, double tol) {
068: if (obj != null && (obj instanceof DoubleSparseVector)
069: && N == ((DoubleSparseVector) obj).N) {
070: DoubleSparseVector v = (DoubleSparseVector) obj;
071: if (pos.length != v.pos.length)
072: return false;
073: double sumSqr = 0.0;
074: for (int i = 0; i < pos.length; i++) {
075: if (pos[i] != v.pos[i])
076: return false;
077: double delta = vector[i] - v.vector[i];
078: sumSqr += delta * delta;
079: }
080: return (sumSqr <= tol * tol);
081: } else
082: return false;
083: }
084:
085: /**
086: * Returns a component of this vector.
087: * @param n index of the vector component
088: * @exception VectorDimensionException If attempting to access an invalid component.
089: */
090: public double getComponent(int n) {
091: if (n < 0 || n >= N)
092: throw new VectorDimensionException(
093: getInvalidComponentMsg(n));
094: for (int k = 0; k < pos.length; k++) {
095: if (pos[k] == n)
096: return vector[k];
097: }
098: return 0.0;
099: }
100:
101: /**
102: * Sets the value of a component of this vector.
103: * @param n index of the vector component
104: * @param x a number
105: * @exception VectorDimensionException If attempting to access an invalid component.
106: */
107: public void setComponent(int n, double x) {
108: if (n < 0 || n >= N)
109: throw new VectorDimensionException(
110: getInvalidComponentMsg(n));
111: if (Math.abs(x) <= GlobalSettings.ZERO_TOL)
112: return;
113: for (int k = 0; k < pos.length; k++) {
114: if (n == pos[k]) {
115: vector[k] = x;
116: return;
117: }
118: }
119: int newPos[] = new int[pos.length + 1];
120: double newVector[] = new double[vector.length + 1];
121: System.arraycopy(pos, 0, newPos, 0, pos.length);
122: System.arraycopy(vector, 0, newVector, 0, pos.length);
123: newPos[pos.length] = n;
124: newVector[vector.length] = x;
125: pos = newPos;
126: vector = newVector;
127: }
128:
129: /**
130: * Returns the l<sup>2</sup>-norm (magnitude).
131: */
132: public double norm() {
133: return Math.sqrt(sumSquares());
134: }
135:
136: /**
137: * Returns the sum of the squares of the components.
138: */
139: public double sumSquares() {
140: double norm = 0.0;
141: for (int k = 0; k < pos.length; k++)
142: norm += vector[k] * vector[k];
143: return norm;
144: }
145:
146: /**
147: * Returns the mass.
148: */
149: public double mass() {
150: double mass = 0.0;
151: for (int k = 0; k < pos.length; k++)
152: mass += vector[k];
153: return mass;
154: }
155:
156: //============
157: // OPERATIONS
158: //============
159:
160: /**
161: * Returns the negative of this vector.
162: */
163: public AbelianGroup.Member negate() {
164: final DoubleSparseVector ans = new DoubleSparseVector(N);
165: ans.vector = new double[vector.length];
166: ans.pos = new int[pos.length];
167: System.arraycopy(pos, 0, ans.pos, 0, pos.length);
168: for (int i = 0; i < pos.length; i++)
169: ans.vector[i] = -vector[i];
170: return ans;
171: }
172:
173: // ADDITION
174:
175: /**
176: * Returns the addition of this vector and another.
177: */
178: public AbelianGroup.Member add(final AbelianGroup.Member v) {
179: if (v instanceof AbstractDoubleVector)
180: return add((AbstractDoubleVector) v);
181: else
182: throw new IllegalArgumentException(
183: "Member class not recognised by this method.");
184: }
185:
186: /**
187: * Returns the addition of this vector and another.
188: * @param v a double vector
189: * @exception VectorDimensionException If the vectors are different sizes.
190: */
191: public AbstractDoubleVector add(final AbstractDoubleVector v) {
192: if (v instanceof DoubleSparseVector)
193: return add((DoubleSparseVector) v);
194: else if (v instanceof DoubleVector)
195: return add((DoubleVector) v);
196: else {
197: if (N != v.N)
198: throw new VectorDimensionException(
199: "Vectors are different sizes.");
200: double array[] = new double[N];
201: array[0] = v.getComponent(0);
202: for (int i = 1; i < N; i++)
203: array[i] = v.getComponent(i);
204: for (int i = 0; i < pos.length; i++)
205: array[pos[i]] += vector[i];
206: return new DoubleVector(array);
207: }
208: }
209:
210: public DoubleVector add(final DoubleVector v) {
211: if (N != v.N)
212: throw new VectorDimensionException(
213: "Vectors are different sizes.");
214: double array[] = new double[N];
215: System.arraycopy(v.vector, 0, array, 0, N);
216: for (int i = 0; i < pos.length; i++)
217: array[pos[i]] += vector[i];
218: return new DoubleVector(array);
219: }
220:
221: /**
222: * Returns the addition of this vector and another.
223: * @param v a double sparse vector
224: * @exception VectorDimensionException If the vectors are different sizes.
225: */
226: public DoubleSparseVector add(final DoubleSparseVector v) {
227: if (N != v.N)
228: throw new VectorDimensionException(
229: "Vectors are different sizes.");
230: double array[] = new double[N];
231: for (int i = 0; i < pos.length; i++)
232: array[pos[i]] = vector[i] + v.getComponent(pos[i]);
233: for (int m, i = 0; i < v.pos.length; i++) {
234: m = v.pos[i];
235: array[m] = getComponent(m) + v.vector[i];
236: }
237: return new DoubleSparseVector(array);
238: }
239:
240: // SUBTRACTION
241:
242: /**
243: * Returns the subtraction of this vector by another.
244: */
245: public AbelianGroup.Member subtract(final AbelianGroup.Member v) {
246: if (v instanceof AbstractDoubleVector)
247: return subtract((AbstractDoubleVector) v);
248: else
249: throw new IllegalArgumentException(
250: "Member class not recognised by this method.");
251: }
252:
253: /**
254: * Returns the subtraction of this vector by another.
255: * @param v a double vector
256: * @exception VectorDimensionException If the vectors are different sizes.
257: */
258: public AbstractDoubleVector subtract(final AbstractDoubleVector v) {
259: if (v instanceof DoubleSparseVector)
260: return subtract((DoubleSparseVector) v);
261: else if (v instanceof DoubleVector)
262: return subtract((DoubleVector) v);
263: else {
264: if (N != v.N)
265: throw new VectorDimensionException(
266: "Vectors are different sizes.");
267: double array[] = new double[N];
268: array[0] = -v.getComponent(0);
269: for (int i = 1; i < N; i++)
270: array[i] = -v.getComponent(i);
271: for (int i = 0; i < pos.length; i++)
272: array[pos[i]] += vector[i];
273: return new DoubleVector(array);
274: }
275: }
276:
277: public DoubleVector subtract(final DoubleVector v) {
278: if (N != v.N)
279: throw new VectorDimensionException(
280: "Vectors are different sizes.");
281: double array[] = new double[N];
282: array[0] = -v.vector[0];
283: for (int i = 1; i < N; i++)
284: array[i] = -v.vector[i];
285: for (int i = 0; i < pos.length; i++)
286: array[pos[i]] += vector[i];
287: return new DoubleVector(array);
288: }
289:
290: /**
291: * Returns the subtraction of this vector by another.
292: * @param v a double sparse vector
293: * @exception VectorDimensionException If the vectors are different sizes.
294: */
295: public DoubleSparseVector subtract(final DoubleSparseVector v) {
296: if (N != v.N)
297: throw new VectorDimensionException(
298: "Vectors are different sizes.");
299: double array[] = new double[N];
300: for (int i = 0; i < pos.length; i++)
301: array[pos[i]] = vector[i] - v.getComponent(pos[i]);
302: for (int m, i = 0; i < v.pos.length; i++) {
303: m = v.pos[i];
304: array[m] = getComponent(m) - v.vector[i];
305: }
306: return new DoubleSparseVector(array);
307: }
308:
309: // SCALAR MULTIPLICATION
310:
311: /**
312: * Returns the multiplication of this vector by a scalar.
313: */
314: public Module.Member scalarMultiply(Ring.Member x) {
315: if (x instanceof MathDouble)
316: return scalarMultiply(((MathDouble) x).value());
317: else if (x instanceof MathInteger)
318: return scalarMultiply(((MathInteger) x).value());
319: else
320: throw new IllegalArgumentException(
321: "Member class not recognised by this method.");
322: }
323:
324: /**
325: * Returns the multiplication of this vector by a scalar.
326: * @param x a double
327: */
328: public AbstractDoubleVector scalarMultiply(final double x) {
329: final DoubleSparseVector ans = new DoubleSparseVector(N);
330: ans.vector = new double[vector.length];
331: ans.pos = new int[pos.length];
332: System.arraycopy(pos, 0, ans.pos, 0, pos.length);
333: for (int i = 0; i < pos.length; i++)
334: ans.vector[i] = x * vector[i];
335: return ans;
336: }
337:
338: // SCALAR DIVISION
339:
340: /**
341: * Returns the division of this vector by a scalar.
342: */
343: public VectorSpace.Member scalarDivide(Field.Member x) {
344: if (x instanceof MathDouble)
345: return scalarDivide(((MathDouble) x).value());
346: else
347: throw new IllegalArgumentException(
348: "Member class not recognised by this method.");
349: }
350:
351: /**
352: * Returns the division of this vector by a scalar.
353: * @param x a double
354: * @exception ArithmeticException If divide by zero.
355: */
356: public AbstractDoubleVector scalarDivide(final double x) {
357: final DoubleSparseVector ans = new DoubleSparseVector(N);
358: ans.vector = new double[vector.length];
359: ans.pos = new int[pos.length];
360: System.arraycopy(pos, 0, ans.pos, 0, pos.length);
361: for (int i = 0; i < pos.length; i++)
362: ans.vector[i] = vector[i] / x;
363: return ans;
364: }
365:
366: // SCALAR PRODUCT
367:
368: /**
369: * Returns the scalar product of this vector and another.
370: * @param v a double vector
371: * @exception VectorDimensionException If the vectors are different sizes.
372: */
373: public double scalarProduct(final AbstractDoubleVector v) {
374: if (v instanceof DoubleSparseVector)
375: return scalarProduct((DoubleSparseVector) v);
376: else if (v instanceof DoubleVector)
377: return scalarProduct((DoubleVector) v);
378: else {
379: if (N != v.N)
380: throw new VectorDimensionException(
381: "Vectors are different sizes.");
382: double ps = 0.0;
383: for (int i = 0; i < pos.length; i++)
384: ps += vector[i] * v.getComponent(pos[i]);
385: return ps;
386: }
387: }
388:
389: public double scalarProduct(final DoubleVector v) {
390: if (N != v.N)
391: throw new VectorDimensionException(
392: "Vectors are different sizes.");
393: double ps = 0.0;
394: for (int i = 0; i < pos.length; i++)
395: ps += vector[i] * v.vector[pos[i]];
396: return ps;
397: }
398:
399: /**
400: * Returns the scalar product of this vector and another.
401: * @param v a double sparse vector
402: * @exception VectorDimensionException If the vectors are different sizes.
403: */
404: public double scalarProduct(final DoubleSparseVector v) {
405: if (N != v.N)
406: throw new VectorDimensionException(
407: "Vectors are different sizes.");
408: double ps = 0.0;
409: if (pos.length <= v.pos.length) {
410: for (int i = 0; i < pos.length; i++)
411: ps += vector[i] * v.getComponent(pos[i]);
412: } else {
413: for (int i = 0; i < v.pos.length; i++)
414: ps += getComponent(v.pos[i]) * v.vector[i];
415: }
416: return ps;
417: }
418:
419: // TENSOR PRODUCT
420:
421: /**
422: * Returns the tensor product of this vector and another.
423: */
424: public DoubleSparseMatrix tensorProduct(final DoubleSparseVector v) {
425: DoubleSparseMatrix ans = new DoubleSparseMatrix(N, v.N);
426: for (int j, i = 0; i < pos.length; i++) {
427: for (j = 0; j < v.pos.length; j++)
428: ans.setElement(pos[i], v.pos[j], vector[i]
429: * v.vector[j]);
430: }
431: return ans;
432: }
433:
434: // MAP COMPONENTS
435:
436: /**
437: * Applies a function on all the vector components.
438: * @param f a user-defined function
439: * @return a double sparse vector
440: */
441: public AbstractDoubleVector mapComponents(final Mapping f) {
442: double zeroValue = f.map(0.0);
443: if (Math.abs(zeroValue) <= GlobalSettings.ZERO_TOL)
444: return sparseMap(f);
445: else
446: return generalMap(f, zeroValue);
447: }
448:
449: private AbstractDoubleVector sparseMap(Mapping f) {
450: final DoubleSparseVector ans = new DoubleSparseVector(N);
451: ans.vector = new double[vector.length];
452: ans.pos = new int[pos.length];
453: System.arraycopy(pos, 0, ans.pos, 0, pos.length);
454: for (int i = 0; i < pos.length; i++)
455: ans.vector[i] = f.map(vector[i]);
456: return ans;
457: }
458:
459: private AbstractDoubleVector generalMap(Mapping f, double zeroValue) {
460: double[] array = new double[N];
461: for (int i = 0; i < N; i++)
462: array[i] = zeroValue;
463: for (int i = 0; i < pos.length; i++)
464: array[i] = f.map(vector[pos[i]]);
465: return new DoubleVector(array);
466: }
467: }
|