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;
}

Two line intersection

yeah gauss jordan works...but it's a metric tonne of code...this is like 3 lines...plus there's some good conversions from different line forms so you don't have to work them out

/**
 * conputes the intersection of two lines given in standard form
 * @param a1
 * @param b1
 * @param c1
 * @param a2
 * @param b2
 * @param c2
 * @return null if parallel, else {x,y}
 * 
 * two points: a=y2-y1, b=x1-x2, c=a*x1+b*y1
 * slope intercept: a=-1*m b=1 c=b
 * point slope: a=-1*m b=1 c=y'-m*x'+b
 */
public double[] lineIntersect(double a1,double b1,double c1,double a2,double b2,double c2){
	double den=a1*b2-a2*b1;
	if(Math.abs(den)<.000001)return null;//parallel
	double x=(b2*c1-b1*c2)/den;
	double y=(a1*c2-a2*c1)/den;
	double[] ans={x,y};
	return ans;
}