/*
* Copyright 2011, Vladimir Kostyukov
*
* This file is part of la4j project (http://la4j.googlecode.com)
*
* Licensed under the Apache License, Version 2.0 (the "License");
* You may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package la4j.decomposition;
import la4j.err.MatrixDecompositionException;
import la4j.factory.Factory;
import la4j.matrix.Matrix;
import la4j.vector.Vector;
public class QRDecompositor implements MatrixDecompositor {
@Override
public Matrix[] decompose(Matrix matrix, Factory factory) throws MatrixDecompositionException {
if (matrix.rows() < matrix.columns()) throw new MatrixDecompositionException();
Matrix qr = matrix.clone();
Vector rdiag = factory.createVector(qr.columns());
for (int k = 0; k < qr.columns(); k++) {
double norm = 0.0;
for (int i = k; i < qr.rows(); i++) {
norm = hypot(norm, qr.get(i, k));
}
if (Math.abs(norm) > EPS) {
if (qr.get(k, k) < 0.0) norm = -norm;
for (int i = k; i < qr.rows(); i++) {
qr.set(i, k, qr.get(i, k) / norm);
}
qr.set(k, k, qr.get(k, k) + 1.0);
for (int j = k + 1; j < qr.columns(); j++) {
double summand = 0.0;
for (int i = k; i < qr.rows(); i++) {
summand += qr.get(i, k) * qr.get(i, j);
}
summand = -summand / qr.get(k, k);
for (int i = k; i < qr.rows(); i++) {
qr.set(i, j, qr.get(i, j) + summand * qr.get(i, k));
}
}
}
rdiag.set(k, norm);
}
Matrix q = factory.createMatrix(qr.rows(), qr.columns());
for (int k = q.columns() - 1; k >= 0; k--) {
q.set(k, k, 1.0);
for (int j = k; j < q.columns(); j++) {
if (Math.abs(qr.get(k, k)) > EPS) {
double summand = 0.0;
for (int i = k; i < q.rows(); i++) {
summand += qr.get(i, k) * q.get(i, j);
}
summand = -summand / qr.get(k, k);
for (int i = k; i < q.rows(); i++) {
q.set(i, j, q.get(i, j) + (summand * qr.get(i, k)));
}
}
}
}
Matrix r = factory.createMatrix(qr.columns(), qr.columns());
for (int i = 0; i < r.columns(); i++) {
for (int j = i; j < r.columns(); j++) {
if (i < j) r.set(i, j, -qr.get(i, j));
else if (i == j) r.set(i, j, rdiag.get(i));
}
}
// TODO: fix it
return new Matrix[] { q.multiply(-1), r };
}
private double hypot(double a, double b) {
double result;
if (Math.abs(a) > Math.abs(b)) {
result = b / a;
result = Math.abs(a) * Math.sqrt(1 + result * result);
} else if (b != 0) {
result = a / b;
result = Math.abs(b) * Math.sqrt(1 + result * result);
} else {
result = 0.0;
}
return result;
}
}