001/*
002 * $Id: GaussElimination.java 4850 2014-06-28 18:26:08Z kredel $
003 */
004
005package edu.jas.jlinalg;
006
007
008import java.util.ArrayList;
009
010import org.jlinalg.AffineLinearSubspace;
011import org.jlinalg.LinSysSolver;
012import org.jlinalg.Matrix;
013import org.jlinalg.Vector;
014import org.jlinalg.polynomial.Polynomial;
015
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.structure.RingElem;
019import edu.jas.vector.GenMatrix;
020import edu.jas.vector.GenMatrixRing;
021import edu.jas.vector.GenVector;
022import edu.jas.vector.GenVectorModul;
023
024
025/**
026 * Algorithms related to Gaussian elimination. Conversion to JLinAlg classes and
027 * delegation to JLinAlg algorithms.
028 * @param <C> coefficient ring element type
029 * @author Heinz Kredel
030 */
031
032public class GaussElimination<C extends RingElem<C>> {
033
034
035    /**
036     * Solve a linear system: a x = b.
037     * @param a matrix
038     * @param b vector of right hand side
039     * @return a solution vector x
040     */
041    public GenVector<C> solve(GenMatrix<C> a, GenVector<C> b) {
042        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
043        Vector<JLAdapter<C>> bv = JLAdapterUtil.<C> toJLAdapterVector(b);
044
045        Vector<JLAdapter<C>> xv = LinSysSolver.solve(am, bv);
046
047        GenVector<C> xa = JLAdapterUtil.<C> vectorFromJLAdapter(b.modul, xv);
048        return xa;
049    }
050
051
052    /**
053     * Null space, generating system of solutions of a linear system: a x = 0.
054     * @param a matrix
055     * @return matrix of generating system of solution vectors x
056     */
057    public GenMatrix<C> nullSpace(GenMatrix<C> a) {
058        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
059
060        GenVectorModul<C> vfac = new GenVectorModul<C>(a.ring.coFac, a.ring.cols);
061        Vector<JLAdapter<C>> bv = JLAdapterUtil.<C> toJLAdapterVector(vfac.getZERO());
062
063        ArrayList<ArrayList<C>> nsl = null;
064        int dim = 0;
065        try {
066            AffineLinearSubspace<JLAdapter<C>> ss = LinSysSolver.solutionSpace(am, bv);
067            //System.out.println("ss = " + ss);
068            try {
069                ss = ss.normalize();
070            } catch (Exception e) {
071                //e.printStackTrace();
072            }
073            Vector<JLAdapter<C>>[] nsa = ss.getGeneratingSystem();
074
075            dim = nsa.length;
076            nsl = new ArrayList<ArrayList<C>>(nsa.length);
077            for (int i = 0; i < nsa.length; i++) {
078                nsl.add(JLAdapterUtil.<C> listFromJLAdapter(nsa[i]));
079            }
080        } catch (Exception e) {
081            //e.printStackTrace();
082            nsl = new ArrayList<ArrayList<C>>();
083        }
084        GenMatrixRing<C> nr;
085        if (dim > 0) {
086            nr = new GenMatrixRing<C>(a.ring.coFac, dim, a.ring.cols);
087        } else {
088            nr = new GenMatrixRing<C>(a.ring.coFac, a.ring.rows, a.ring.cols);
089        }
090        GenMatrix<C> ns = new GenMatrix<C>(nr, nsl);
091        if (dim > 0) {
092            nr = nr.transpose();
093            ns = ns.transpose(nr); // column vectors
094        }
095        return ns;
096    }
097
098
099    /**
100     * Test if n is a null space for the linear system: a n = 0.
101     * @param a matrix
102     * @param n matrix
103     * @return true, if n is a nullspace of a, else false
104     */
105    public boolean isNullSpace(GenMatrix<C> a, GenMatrix<C> n) {
106        GenMatrix<C> z = a.multiply(n); // .transpose(n.ring) better not transpose here
107        //System.out.println("z = " + z);
108        return z.isZERO();
109    }
110
111
112    /**
113     * Characteristic polynomial of a matrix.
114     * @param a matrix
115     * @return characteristic polynomial of a
116     */
117    public GenPolynomial<C> characteristicPolynomial(GenMatrix<C> a) {
118        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
119
120        Polynomial<JLAdapter<C>> p = am.characteristicPolynomial();
121
122        GenPolynomialRing<C> pfac = new GenPolynomialRing<C>(a.ring.coFac, new String[] { "x" });
123        GenPolynomial<C> cp = pfac.parse(p.toString());
124        return cp;
125    }
126
127
128    /**
129     * Determinant of a matrix.
130     * @param a matrix
131     * @return determinant of a
132     */
133    public C determinant(GenMatrix<C> a) {
134        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
135        JLAdapter<C> dm = am.det();
136        C d = dm.val;
137        return d;
138    }
139
140
141    /**
142     * Trace of a matrix.
143     * @param a matrix
144     * @return trace of a
145     */
146    public C trace(GenMatrix<C> a) {
147        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
148        JLAdapter<C> dm = am.trace();
149        C d = dm.val;
150        return d;
151    }
152
153
154    /**
155     * Rank of a matrix.
156     * @param a matrix
157     * @return rank of a
158     */
159    public int rank(GenMatrix<C> a) {
160        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
161        int r = am.rank();
162        return r;
163    }
164
165
166    /**
167     * Gauss elimination of a matrix.
168     * @param a matrix
169     * @return Gauss elimination of a
170     */
171    public GenMatrix<C> gaussElimination(GenMatrix<C> a) {
172        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
173        Matrix<JLAdapter<C>> bm = am.gausselim();
174        GenMatrix<C> g = JLAdapterUtil.<C> matrixFromJLAdapter(a.ring, bm);
175        return g;
176    }
177
178
179    /**
180     * Gauss-Jordan elimination of a matrix.
181     * @param a matrix
182     * @return Gauss-Jordan elimination of a
183     */
184    public GenMatrix<C> gaussJordanElimination(GenMatrix<C> a) {
185        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
186        Matrix<JLAdapter<C>> bm = am.gaussjord();
187        GenMatrix<C> g = JLAdapterUtil.<C> matrixFromJLAdapter(a.ring, bm);
188        return g;
189    }
190
191
192    /**
193     * Inverse of a matrix.
194     * @param a matrix
195     * @return inverse matrix of a
196     */
197    public GenMatrix<C> inverse(GenMatrix<C> a) {
198        Matrix<JLAdapter<C>> am = JLAdapterUtil.<C> toJLAdapterMatrix(a);
199        Matrix<JLAdapter<C>> bm = am.inverse();
200        GenMatrix<C> g = JLAdapterUtil.<C> matrixFromJLAdapter(a.ring, bm);
201        return g;
202    }
203
204}