Linear Equations

gauss-jordan elimination

Credit Siyang Chen

/**
 * solves A*X=b
 * @param A coefficients
 * @param b constants
 * @return values of the variables
 */
public double[] linearEquationSolve( double[][] A, double[] b ){
	double EPS=.000001;//or whatever you need it to be
	int n = A.length;
	double a[][] = new double[n][n+1], temp[], scale;
	for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) a[i][j] = A[i][j];
	for( int i = 0; i < n; i++ ) a[i][n] = b[i];
	for( int i = 0; i < n; i++ ){
		for( int j = i; j < n; j++ )if( Math.abs(a[j][i])>EPS ){
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;
				break;
		}
		scale = 1/a[i][i];
		for( int j = i; j <= n; j++ ) a[i][j] *= scale;
		for( int j = 0; j < n; j++ )if( i != j && Math.abs(a[j][i])>EPS ){
			scale = -a[j][i];
			for( int k = i; k <= n; k++ ) a[j][k] += scale*a[i][k];
		}
	}
	double[] x = new double[n];
	for( int i = 0; i < n; i++ ) x[i] = a[i][n];
	return x;
}

determinant

This was a clever way to do this...it's recursion with memoization, where somehow mask represents a subproblem and the solution is stored in dp. Mask represents the already used columns, and thus implicitly defines the minor matrix for which we're calculating the determinant

/**
 * finds the determinant of the input matrix
 * @param d the input matrix
 * @param row 0 to start with
 * @param mask 0 to start with
 * @param dp -1 filled array of the same length as ((1<<d.length)-1)
 * @return the value of the determinant
 */
public long det(int[][] d, int row, int mask, long[] dp) {
	if(row == d.length)return 1;
	if(dp[mask]>0)return dp[mask];
	int sign=1;
	long ans=0;
	for(int i=0;i<d.length;i++){
		if(((mask>>i)&1)==0){
			ans+=sign*d[row][i]*det(d,row+1,mask|(1<<i),dp);
			sign*=-1;
		}
	}
	dp[mask]=ans;
	return ans;
}