using System;

public class givens{

public static void qr_inplace(matrix A){
	for(int p=0;p<A.size2;p++)for(int q=p+1;q<A.size1;q++){
		double t=Math.Atan2(A[q,p],A[p,p]);
		double c=Math.Cos(t), s=Math.Sin(t);
		for(int k=p;k<A.size2;k++){
			double xp=A[p,k], xq=A[q,k];
			A[p,k]= xp*c+xq*s;
			A[q,k]=-xp*s+xq*c;
			}
			A[q,p]=t;
		}
	}

public static void apply_QT_inplace(matrix A, vector x){
	for(int q=0;q<A.size2;q++)for(int p=q+1;p<A.size1;p++){
		double t = A[p,q], xq=x[q], xp=x[p];
		double c=Math.Cos(t), s=Math.Sin(t);
		x[q]= xq*c+xp*s;
		x[p]=-xq*s+xp*c;
		}
	}

public static vector apply_QT(matrix A, vector b){
	vector c=b.copy();
	apply_QT_inplace(A,c);
	vector x=new vector(A.size2);
	for(int i=0;i<x.size;i++)x[i]=c[i];
	return x;
	}

public static vector solve(matrix A, vector b){
	vector x = apply_QT(A,b);
	for(int i=x.size-1;i>=0;i--){
		double s=0; for(int k=i+1;k<x.size;k++) s+=A[i,k]*x[k];
		x[i]=(x[i]-s)/A[i,i];
		}
	return x;
	}

public static void inverse(matrix A, matrix B){
	vector b=new vector(B.size1);
	for (int i=0; i<B.size2; i++){
		b[i]=1;
		B[i]=solve(A,b);
		b[i]=0;
		}
	}

public static matrix unpack_Q(matrix A){
	matrix Q = new matrix(A.size1,A.size2);
	vector ei = new vector(A.size1);
	for(int i=0;i<A.size1;i++){
		ei.set_basis(i);
		apply_QT_inplace(A,ei);
		for(int j=0;j<A.size2;j++) Q[i,j]=ei[j];
		}
	return Q;
	}

public static matrix unpack_R(matrix A){
	int m=A.size2;
	matrix R = new matrix(m,m);
	for(int c=0;c<m;c++) for(int r=0;r<=c;r++) R[r,c]=A[r,c];
	return R;
}


}