gistfile1.java

package com.timdumol.algos.numerical;

import java.io.*;
import java.util.*;
import static java.lang.System.*;

public class GaussianElimination {
	public static double[] gaussian(double[][] a, double[] b) {
		for (int i = 0; i < a.length - 1; ++i) {
			{
				double max = a[i][i];
				int max_idx = i;
				for (int j = i + 1; j < a.length; ++j) {
					if (a[j][i] > max) {
						max = a[j][i];
						max_idx = j;
					}
				}
				double[] tmp = a[max_idx];
				a[max_idx] = a[i];
				a[i] = tmp;
				double tmp2 = b[max_idx];
				b[max_idx] = b[i];
				b[i] = tmp2;
			}
			double pivot = a[i][i];
			if (pivot < 1e-10) return new double[0];
			for (int j = i + 1; j < a.length; ++j) {
				double q = a[j][i] / pivot;
				a[j][i] = 0;
				for (int k = i + 1; k < a[j].length; ++k) {
					a[j][k] -= q * a[i][k];
				}
				b[j] -= b[i] * q;
			}
		}

		double[] x = new double[b.length];
		// Backward substitution
		for (int i = a.length - 1; i >= 0; --i) {
			x[i] = b[i];
			for (int j = a.length - 1; j > i; --j) {
				x[i] -= x[j] * a[i][j];
			}
			x[i] /= a[i][i];
		}
		return x;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		PrintStream ps = out;
		String[] s = br.readLine().split(" ");
		int m = Integer.valueOf(s[0]);
		int n = Integer.valueOf(s[1]);
		double[][] mat = new double[n][m];
		double[] b = new double[n];
		for (int i = 0; i < n; ++i) {
			s = br.readLine().split(" ");
			for (int j = 0; j < m; ++j) {
				mat[i][j] = Double.valueOf(s[j]);
			}
		}
		for (int i = 0; i < n; ++i) {
			b[i] = Double.valueOf(br.readLine());
		}
		ps.println(Arrays.toString(gaussian(mat, b)));
	}

}