Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.vector;
006
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Iterator;
011import java.util.List;
012
013import org.apache.logging.log4j.LogManager;
014import org.apache.logging.log4j.Logger;
015
016import edu.jas.structure.RingElem;
017
018
019/**
020 * Basic linear algebra methods. Implements Basic linear algebra computations
021 * and tests. <b>Note:</b> will eventually use wrong method dispatch in JRE when
022 * used with GenSolvablePolynomial.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026public class BasicLinAlg<C extends RingElem<C>> implements Serializable {
027
028
029    private static final Logger logger = LogManager.getLogger(BasicLinAlg.class);
030
031
032    //private static final boolean debug = logger.isDebugEnabled();
033
034
035    /**
036     * Constructor.
037     */
038    public BasicLinAlg() {
039    }
040
041
042    /**
043     * Scalar product of vectors of ring elements.
044     * @param G a ring element list.
045     * @param F a ring element list.
046     * @return the scalar product of G and F.
047     */
048    public C scalarProduct(List<C> G, List<C> F) {
049        C sp = null;
050        Iterator<C> it = G.iterator();
051        Iterator<C> jt = F.iterator();
052        while (it.hasNext() && jt.hasNext()) {
053            C pi = it.next();
054            C pj = jt.next();
055            if (pi == null || pj == null) {
056                continue;
057            }
058            if (sp == null) {
059                sp = pi.multiply(pj);
060            } else {
061                sp = sp.sum(pi.multiply(pj));
062            }
063        }
064        if (it.hasNext() || jt.hasNext()) {
065            logger.error("scalarProduct wrong sizes");
066        }
067        return sp;
068    }
069
070
071    /**
072     * Scalar product of vectors and a matrix of ring elements.
073     * @param G a ring element list.
074     * @param F a list of ring element lists.
075     * @return the scalar product of G and F.
076     */
077    public List<C> leftScalarProduct(List<C> G, List<List<C>> F) {
078        List<C> sp = null; //new ArrayList<C>(G.size());
079        Iterator<C> it = G.iterator();
080        Iterator<List<C>> jt = F.iterator();
081        while (it.hasNext() && jt.hasNext()) {
082            C pi = it.next();
083            List<C> pj = jt.next();
084            if (pi == null || pj == null) {
085                continue;
086            }
087            List<C> s = scalarProduct(pi, pj);
088            if (sp == null) {
089                sp = s;
090            } else {
091                sp = vectorAdd(sp, s);
092            }
093        }
094        if (it.hasNext() || jt.hasNext()) {
095            logger.error("scalarProduct wrong sizes");
096        }
097        return sp;
098    }
099
100
101    /**
102     * Scalar product of vectors and a matrix of ring elements.
103     * @param G a ring element list.
104     * @param F a list of ring element lists.
105     * @return the right scalar product of G and F.
106     */
107    public List<C> rightScalarProduct(List<C> G, List<List<C>> F) {
108        List<C> sp = null; //new ArrayList<C>(G.size());
109        Iterator<C> it = G.iterator();
110        Iterator<List<C>> jt = F.iterator();
111        while (it.hasNext() && jt.hasNext()) {
112            C pi = it.next();
113            List<C> pj = jt.next();
114            if (pi == null || pj == null) {
115                continue;
116            }
117            List<C> s = scalarProduct(pj, pi);
118            if (sp == null) {
119                sp = s;
120            } else {
121                sp = vectorAdd(sp, s);
122            }
123        }
124        if (it.hasNext() || jt.hasNext()) {
125            logger.error("scalarProduct wrong sizes");
126        }
127        return sp;
128    }
129
130
131    /**
132     * Addition of vectors of ring elements.
133     * @param a a ring element list.
134     * @param b a ring element list.
135     * @return a+b, the vector sum of a and b.
136     */
137    public List<C> vectorAdd(List<C> a, List<C> b) {
138        if (a == null) {
139            return b;
140        }
141        if (b == null) {
142            return a;
143        }
144        List<C> V = new ArrayList<C>(a.size());
145        Iterator<C> it = a.iterator();
146        Iterator<C> jt = b.iterator();
147        while (it.hasNext() && jt.hasNext()) {
148            C pi = it.next();
149            C pj = jt.next();
150            C p = pi.sum(pj);
151            V.add(p);
152        }
153        //System.out.println("vectorAdd" + V);
154        if (it.hasNext() || jt.hasNext()) {
155            logger.error("vectorAdd wrong sizes");
156        }
157        return V;
158    }
159
160
161    /**
162     * Negative of vectors of ring elements.
163     * @param a a ring element list.
164     * @return -a, the vector of -a.
165     */
166    public List<C> vectorNegate(List<C> a) {
167        if (a == null) {
168            return a;
169        }
170        List<C> V = new ArrayList<C>(a.size());
171        Iterator<C> it = a.iterator();
172        while (it.hasNext()) {
173            C pi = it.next();
174            if (pi != null) {
175                pi = pi.negate();
176            }
177            V.add(pi);
178        }
179        //System.out.println("vectorNegate" + V);
180        return V;
181    }
182
183
184    /**
185     * Combination of vectors for reduction representation.
186     * @param a a ring element list.
187     * @param b a ring element list.
188     * @return a-b, the vector difference of a and b, with one entry more.
189     */
190    public List<C> vectorCombineRep(List<C> a, List<C> b) {
191        if (a == null || b == null) {
192            throw new IllegalArgumentException("a and b may not be empty");
193        }
194        // if (a.size() != b.size()) {
195        //     throw new IllegalArgumentException("#a != #b");
196        // }
197        List<C> V = new ArrayList<C>(a.size() + 1);
198        Iterator<C> it = a.iterator();
199        Iterator<C> jt = b.iterator();
200        while (it.hasNext() && jt.hasNext()) {
201            C x = it.next();
202            C y = jt.next();
203            if (x == null) {
204                if (y == null) {
205                    //x = y;
206                } else {
207                    x = y.negate();
208                }
209            } else {
210                if (y == null) {
211                    //x = y;
212                } else {
213                    x = x.subtract(y);
214                }
215            }
216            V.add(x);
217        }
218        if (it.hasNext() || jt.hasNext()) {
219            logger.error("vectorCombineRep wrong sizes: it = {}, jt = {}", it, jt);
220            //throw new RuntimeException("it = " + it + ", jt = " + jt);
221        }
222        V.add(null);
223        //System.out.println("vectorCombineRep" + V);
224        return V;
225    }
226
227
228    /**
229     * Combination of vectors for syzygy representation.
230     * @param a a ring element list.
231     * @param b a ring element list.
232     * @return (-a)+b, the vector sum of -a and b, with one entry more.
233     */
234    public List<C> vectorCombineSyz(List<C> a, List<C> b) {
235        if (a == null || b == null) {
236            throw new IllegalArgumentException("a and b may not be empty");
237        }
238        // if (a.size() != b.size()) {
239        //     throw new IllegalArgumentException("#a != #b");
240        // }
241        List<C> V = new ArrayList<C>(a.size() + 1);
242        Iterator<C> it = a.iterator();
243        Iterator<C> jt = b.iterator();
244        while (it.hasNext() && jt.hasNext()) {
245            C x = it.next();
246            C y = jt.next();
247            if (x == null) {
248                if (y == null) {
249                    //x = y;
250                } else {
251                    x = y;
252                }
253            } else {
254                if (y == null) {
255                    //x = y;
256                } else {
257                    x = x.sum(y);
258                }
259            }
260            V.add(x);
261        }
262        if (it.hasNext() || jt.hasNext()) {
263            logger.error("vectorCombineSyz wrong sizes: it = {}, jt = {}", it, jt);
264            //throw new RuntimeException("it = " + it + ", jt = " + jt);
265        }
266        V.add(null);
267        //System.out.println("vectorCombineSyz" + V);
268        return V;
269    }
270
271
272    /**
273     * Combination of vectors for old representation.
274     * @param a a ring element list.
275     * @param b a ring element list.
276     * @return -a-b, the vector difference of -a and b, with one entry more.
277     */
278    public List<C> vectorCombineOld(List<C> a, List<C> b) {
279        if (a == null || b == null) {
280            throw new IllegalArgumentException("a and b may not be empty");
281        }
282        // if (a.size() != b.size()) {
283        //     throw new IllegalArgumentException("#a != #b");
284        // }
285        List<C> V = new ArrayList<C>(a.size() + 1);
286        Iterator<C> it = a.iterator();
287        Iterator<C> jt = b.iterator();
288        while (it.hasNext() && jt.hasNext()) {
289            C x = it.next();
290            C y = jt.next();
291            if (x != null) {
292                //System.out.println("ms = " + m + " " + x);
293                x = x.negate();
294            }
295            if (y != null) {
296                y = y.negate();
297                //System.out.println("mh = " + m + " " + y);
298            }
299            if (x == null) {
300                x = y;
301            } else if (y != null) {
302                x = x.sum(y);
303            }
304            //System.out.println("mx = " + m + " " + x);
305            V.add(x);
306        }
307        if (it.hasNext() || jt.hasNext()) {
308            logger.error("vectorCombineOld wrong sizes: it = {}, jt = {}", it, jt);
309            //throw new RuntimeException("it = " + it + ", jt = " + jt);
310        }
311        V.add(null);
312        //System.out.println("vectorCombineOld" + V);
313        return V;
314    }
315
316
317    /**
318     * Generation of a vector of ring elements.
319     * @param n length of vector.
320     * @param a a ring element to fill vector entries.
321     * @return V, a vector of length n and entries a.
322     */
323    public List<C> genVector(int n, C a) {
324        List<C> V = new ArrayList<C>(n);
325        if (n == 0) {
326            return V;
327        }
328        for (int i = 0; i < n; i++) {
329            V.add(a);
330        }
331        return V;
332    }
333
334
335    /**
336     * Generation of a vector of ring elements.
337     * @param n length of vector.
338     * @param a a ring element to fill vector entries.
339     * @param A vector of starting first entries.
340     * @return V, a vector of length n and entries a, respectively A.
341     */
342    public List<C> genVector(int n, C a, List<C> A) {
343        List<C> V = new ArrayList<C>(n);
344        if (n == 0) {
345            return V;
346        }
347        int i = 0;
348        for (C b : A) {
349            if (i < n) {
350                V.add(b);
351            } else {
352                break;
353            }
354            i++;
355        }
356        for (int j = A.size(); j < n; j++) {
357            V.add(a);
358        }
359        return V;
360    }
361
362
363    /**
364     * Test vector of zero ring elements.
365     * @param a a ring element list.
366     * @return true, if all polynomial in a are zero, else false.
367     */
368    public boolean isZero(List<C> a) {
369        if (a == null) {
370            return true;
371        }
372        for (C pi : a) {
373            if (pi == null) {
374                continue;
375            }
376            if (!pi.isZERO()) {
377                return false;
378            }
379        }
380        return true;
381    }
382
383
384    /**
385     * Scalar product of ring element with vector of ring elements.
386     * @param p a ring element.
387     * @param F a ring element list.
388     * @return the scalar product of p and F.
389     */
390    public List<C> scalarProduct(C p, List<C> F) {
391        List<C> V = new ArrayList<C>(F.size());
392        for (C pi : F) {
393            if (p != null) {
394                pi = p.multiply(pi);
395            } else {
396                pi = null;
397            }
398            V.add(pi);
399        }
400        return V;
401    }
402
403
404    /**
405     * Scalar product of vector of ring element with ring element.
406     * @param F a ring element list.
407     * @param p a ring element.
408     * @return the scalar product of F and p.
409     */
410    public List<C> scalarProduct(List<C> F, C p) {
411        List<C> V = new ArrayList<C>(F.size());
412        for (C pi : F) {
413            if (pi != null) {
414                pi = pi.multiply(p);
415            }
416            V.add(pi);
417        }
418        return V;
419    }
420
421
422    /**
423     * Product of a vector and a matrix of ring elements.
424     * @param G a vectors of ring elements.
425     * @param F a matrix of ring element lists.
426     * @return the left product of G and F.
427     */
428    public GenVector<C> leftProduct(GenVector<C> G, GenMatrix<C> F) {
429        ArrayList<C> sp = new ArrayList<C>(G.val.size());
430        Iterator<ArrayList<C>> jt = F.matrix.iterator();
431        while (jt.hasNext()) {
432            ArrayList<C> pj = jt.next();
433            if (pj == null) {
434                continue;
435            }
436            C s = scalarProduct(G.val, pj);
437            sp.add(s);
438        }
439        return new GenVector<C>(G.modul, sp);
440    }
441
442
443    /**
444     * Product of a vector and a matrix of ring elements.
445     * @param G a vector of element list.
446     * @param F a matrix of ring element lists.
447     * @return the right product of G and F.
448     */
449    public GenVector<C> rightProduct(GenVector<C> G, GenMatrix<C> F) {
450        ArrayList<C> sp = new ArrayList<C>(G.val.size());
451        Iterator<ArrayList<C>> jt = F.matrix.iterator();
452        while (jt.hasNext()) {
453            ArrayList<C> pj = jt.next();
454            if (pj == null) {
455                continue;
456            }
457            C s = scalarProduct(pj, G.val);
458            sp.add(s);
459        }
460        return new GenVector<C>(G.modul, sp);
461    }
462
463}