3
\$\begingroup\$

Given a set of \$k\$ \$n\$-vectors \$\vec{x_1}, \dots, \vec{x_k}\$, Gram-Schmidt process computes a basis \$\vec{y_1}, \dots, \vec{y_m}\$ (\$m \leq k\$) the vectors of which span the same space as \$\vec{x_1}, \dots, \vec{x_k}\$ but are mutually orthogonal: the inner product \$\vec{y_i}\cdot\vec{y_j} = 0\$ for all \$i \neq j\$. $$ \vec{x} \cdot \vec{y} = \sum_{r = 1}^n x_r y_r. $$

Below is my code:

net.coderodde.math.Additive

package net.coderodde.math;

/**
 * This interface defines the API for adding the two elements.
 * 
 * @param <I1> the type of the left operand.
 * @param <I2> the type of the right operand.
 * @param <O>  the sum type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public interface Additive<I1, I2, O> {

    /**
     * This method adds {@code a} and {@code b} and returns the sum.
     * 
     * @param a the first element.
     * @param b the second element.
     * @return the sum of the two given numbers.
     */
    public O add(I1 a, I2 b);
}

net.coderodde.math.Demo

package net.coderodde.math;

import net.coderodde.math.impl.ComplexVectorProductByScalar;
import net.coderodde.math.impl.ComplexNumber;
import net.coderodde.math.impl.ComplexVectorAdditive;
import net.coderodde.math.impl.ComplexVectorDivisible;
import net.coderodde.math.impl.ComplexVectorInnerProduct;
import net.coderodde.math.impl.ComplexVectorNegative;
import net.coderodde.math.impl.RealVectorAdditive;
import net.coderodde.math.impl.RealVectorDivisible;
import net.coderodde.math.impl.RealVectorInnerProduct;
import net.coderodde.math.impl.RealVectorNegative;
import net.coderodde.math.impl.RealVectorProductByScalar;

/**
 * This class runs a simple demo for the Gram-Schmidt process.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
final class Demo {

    public static void main(String[] args) {
        Vector<Double> x1 = new Vector<>(1., -1., 1., -1.);
        Vector<Double> x2 = new Vector<>(5., 1., 1., 1.);
        Vector<Double> x3 = new Vector<>(-3., -3., 1., -3.);

        Vector<Double>[] orthogonalBasis1 = 
                new GramSchmidtProcess<>(new RealVectorInnerProduct(),
                                         new RealVectorDivisible(),
                                         new RealVectorProductByScalar(),
                                         new RealVectorAdditive(),
                                         new RealVectorNegative())
                .process(x1, x2, x3);

        for (Vector<Double> vector : orthogonalBasis1) {
            System.out.println(vector);
        }

        System.out.println("Orthogonal: " + 
                isOrthogonal(orthogonalBasis1[0],
                             orthogonalBasis1[1],
                             0.00001));

        System.out.println("------");

        // [(1, -2), (3, 4)] = [1 - 2i, 3 + 4i]
        Vector<ComplexNumber> c1 = new Vector<>(new ComplexNumber(1, -2),
                                                new ComplexNumber(3, 4));

        // [(0, -3), (1, 1)] = [-3i, 1 + i]
        Vector<ComplexNumber> c2 = new Vector<>(new ComplexNumber(0, -3),
                                                new ComplexNumber(1, 1));

        Vector<ComplexNumber>[] orthogonalBasis2 = 
                new GramSchmidtProcess<>(new ComplexVectorInnerProduct(),
                                         new ComplexVectorDivisible(),
                                         new ComplexVectorProductByScalar(),
                                         new ComplexVectorAdditive(),
                                         new ComplexVectorNegative())
                .process(c1, c2);

        for (Vector<ComplexNumber> c : orthogonalBasis2) {
            System.out.println(c);
        }        

        System.out.println("Orthogonal: " + 
                isOrthogonalComplex(orthogonalBasis2[0],
                                    orthogonalBasis2[1],
                                    0.00001));
    }

    public static <E, IP> boolean basisIsOrthogonal(Vector<Double>[] basis,
                                                   double epsilon) {
        for (int i = 1; i < basis.length; i++) {
            Vector<Double> target = basis[i];

            for (int j = 0; j < i; j++) {
                Vector<Double> current = basis[j];

                if (!isOrthogonal(target, current, epsilon)) {
                    return false;
                }
            }
        }

        return true;
    }

    public static boolean basisIsOrthogonalComplex(
            Vector<ComplexNumber>[] basis, double epsilon) {
        for (int i = 1; i < basis.length; i++) {
            Vector<ComplexNumber> target = basis[i];

            for (int j = 0; j < i; j++) {
                Vector<ComplexNumber> current = basis[j];

                if (!isOrthogonalComplex(target, current, epsilon)) {
                    return false;
                }
            }
        }

        return true;
    }

    private static boolean isOrthogonal(Vector<Double> a, Vector<Double> b, double epsilon) {
        double sum = 0.0;

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            sum += a.get(i) * b.get(i);
        }

        return sum < epsilon;
    }

    private static boolean isOrthogonalComplex(Vector<ComplexNumber> a,
                                               Vector<ComplexNumber> b,
                                               double epsilon) {
        ComplexNumber sum = new ComplexNumber(0, 0);

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            ComplexNumber product = a.get(i).multiply(b.get(i));
            sum = sum.add(product);
        }

        return Math.abs(sum.getRealPart()) < epsilon &&
               Math.abs(sum.getImaginaryPart()) < epsilon;
    }
}

net.coderodde.math.Divisible

package net.coderodde.math;

/**
 * This interface defines the API for division operator.
 * 
 * @param <D1> the type of the divident.
 * @param <D2> the type of the divisor.
 * @param <F>  the fraction type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public interface Divisible<D1, D2, F> {

    /**
     * Divides {@code a} by {@code b} and returns the result.
     * 
     * @param divident the object being divided.
     * @param divisor  the divisor.
     * @return the result of dividing {@code divident} by {@code divisor}.
     */
    public F divide(D1 divident, D2 divisor);
}

net.coderodde.math.GramSchmidtProcess

package net.coderodde.math;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements the method for running 
 * <a href="">https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process</a>
 * over a given independent basis of a linear space.
 * 
 * @param <VCT> the vertex component type.
 * @param <IPT> the inner product type.
 * @param <FT>  the division result type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public class GramSchmidtProcess<VCT, IPT, FT> {

    /**
     * This object is responsible for computing the inner product of two 
     * vectors.
     */
    private InnerProduct<VCT, VCT, IPT> innerProduct;

    /**
     * This object is responsible for computing division.
     */
    private Divisible<IPT, IPT, FT> divisible;

    /**
     * This object is responsible for computing products (multiplication).
     */
    private Product<FT, Vector<VCT>, Vector<VCT>> product;

    /**
     * This object is responsible for computing addition.
     */
    private Additive<Vector<VCT>, Vector<VCT>, Vector<VCT>> additive;

    /**
     * This object is responsible for computing negative elements.
     */
    private Negative<Vector<VCT>, Vector<VCT>> negative;

    /**
     * Constructs the object with the method for running Gram-Schmidt process 
     * over given basis.
     * 
     * @param innerProduct the object for computing inner products.
     * @param divisible    the object for performing division.
     * @param product      the object for performing multiplication.
     * @param additive     the object for performing addition.
     * @param negative     the object for computing inverses.
     */
    public GramSchmidtProcess(InnerProduct<VCT, VCT, IPT> innerProduct,
                              Divisible<IPT, IPT, FT> divisible,
                              Product<FT, Vector<VCT>, Vector<VCT>> product,
                              Additive<Vector<VCT>,
                                       Vector<VCT>,
                                       Vector<VCT>> additive,
                              Negative<Vector<VCT>, Vector<VCT>> negative) {
        this.innerProduct = 
                Objects.requireNonNull(
                        innerProduct,
                        "The input InnerProduct is null.");

        this.negative = Objects.requireNonNull(negative,  
                                               "The input Negative is null.");

        this.product = Objects.requireNonNull(product, 
                                              "The input Product is null.");

        this.divisible = Objects.requireNonNull(divisible, 
                                                "The input Divisible is null.");

        this.additive = Objects.requireNonNull(additive,
                                               "The input Additive is null.");
    }

    /**
     * Performs the Gram-Schmidt process upon {@code basis}.
     * 
     * @param basis the basis to process.
     * @return the orthogonal basis.
     */
    public Vector<VCT>[] process(Vector<VCT>... basis) {
        // Validate the input basis:
        checkBasis(basis);

        // Deal with the very first base element:
        Vector<VCT>[] orthogonalBasis = new Vector[basis.length];
        orthogonalBasis[0] = (Vector<VCT>) new Vector(basis[0]);

        // The actual process:
        for (int i = 1; i < basis.length; i++) {
            // Copy-construct 'x' from 'basis[i]':
            Vector<VCT> x = new Vector<>(basis[i]);

            // For each basis element before 'x', do:
            for (int j = 0; j < i; j++) {
                // Take the inner product of the divident:
                IPT innerProductDivident = 
                        this.innerProduct.innerProductOf(x, orthogonalBasis[j]);

                // Take the inner product of the divisor:
                IPT innerProductDivisor = 
                        this.innerProduct.innerProductOf(orthogonalBasis[j],
                                                         orthogonalBasis[j]);

                // Divide the divident by divisor:
                FT fraction = divisible.divide(innerProductDivident,
                                               innerProductDivisor);

                // Multiply the above by the current basis:
                Vector<VCT> term = product.multiply(fraction, basis[j]);

                // Negate the above:
                term = negative.negate(term);

                // Add the above to 'x'. Effectively, it subtracts 'term' from
                // 'x' since we have negated 'term':
                x = additive.add(x, term);
            }

            orthogonalBasis[i] = x;
        }

        // Remove the duplicates and return whatever is left:
        return removeDuplicates(orthogonalBasis);
    }

    /**
     * This method validates the input data sent to the Gram-Schmidt process
     * implementation above.
     * 
     * @param <E>            the element component type.
     * @param basisCandidate the basis candidate.
     * @throws IllegalArgumentException if the candidate is not valid.
     */
    private static <E> void checkBasis(Vector<E>[] basisCandidate) {
        // Check not null:
        Objects.requireNonNull(basisCandidate, "The input basis is null.");

        // Check is not empty:
        if (basisCandidate.length == 0) {
            throw new IllegalArgumentException("No vectors given.");
        }

        int expectedDimensions = basisCandidate[0].getNumberOfDimensions();

        // Each element in the basis candidate must have the same 
        // dimensionality:
        if (expectedDimensions == 0) {
            throw new IllegalArgumentException(
                    "The element at index 0 has no components.");
        }

        for (int i = 1; i < basisCandidate.length; i++) {
            if (basisCandidate[i].getNumberOfDimensions() == 0) {
                // Oops. An empty element:
                throw new IllegalArgumentException(
                        "The element at index " + i + " has no components.");
            }

            if (expectedDimensions
                    != basisCandidate[i].getNumberOfDimensions()) {
                // Oops. Not all basis elements are of the same equal 
                // dimensionality:
                throw new IllegalArgumentException(
                    "Element dimension mismatch: expected " +
                            expectedDimensions + " but was " + 
                            basisCandidate[i].getNumberOfDimensions() +
                            " at index " + i + ".");
            }
        }
    }

    private static <E> Vector<E>[] removeDuplicates(Vector<E>[] basis) {
        Set<Vector<E>> set = new HashSet<>(Arrays.asList(basis));
        Vector<E>[] vectors = new Vector[set.size()];
        return set.toArray(vectors);
    }
}

net.coderodde.math.InnerProduct

package net.coderodde.math;

/**
 * This interface defines the API for inner product over given vector component
 * type.
 * 
 * @param <VCT1> the left vector type.
 * @param <VCT2> the right vector type.
 * @param <IPT>  the inner product value type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public interface InnerProduct<VCT1, VCT2, IPT> {

    /**
     * Computes the inner product of the two given vectors.
     * 
     * @param a the first vector.
     * @param b the second vector.
     * @return the inner product 
     */
    public IPT innerProductOf(Vector<VCT1> a, Vector<VCT2> b);
}

net.coderodde.math.Negative

    package net.coderodde.math;

/**
 * This interface defines the API for computing negative of given values.
 * 
 * @param <I> the input type.
 * @param <O> the output type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public interface Negative<I, O> {

    /**
     * Returns the negative of {@code element}. The negative of {@code a} is 
     * {@code -a} such that {@code a + (-a) = O}, where {@code O} is the zero
     * element.
     * 
     * @param element the element to negate.
     * @return the negative of {@code element}.
     */
    public O negate(I element);
}

net.coderodde.math.Product

package net.coderodde.math;

/**
 * This interface defines the API for multiplication (product).
 * 
 * @param <E1> the type of the left element to multiply.
 * @param <E2> the type of the right element to multiply.
 * @param <O>  the product result type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public interface Product<E1, E2, O> {

    /**
     * Returns the product of {@code a} and {@code b}.
     * 
     * @param a the first element.
     * @param b the second element.
     * @return the product of the two input elements.
     */
    public O multiply(E1 a, E2 b);
}

net.coderodde.math.Vector

package net.coderodde.math;

import java.util.Arrays;
import java.util.Objects;

/**
 * This class implements a vector/element in a {@code n}-dimensional space.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public final class Vector<E> {

    /**
     * The actual vector contents.
     */
    private final E[] components;

    /**
     * Constructs the vector from the given data.
     * 
     * @param components the vector data.
     */
    public Vector(E... components) {
        Objects.requireNonNull(components, "The input vector is null.");
        this.components = Arrays.copyOf(components, components.length);
    }

    /**
     * Copy-constructs this vector.
     * 
     * @param vector the vector to copy.
     */
    public Vector(Vector<E> vector) {
        this.components = Arrays.copyOf(vector.components, 
                                        vector.components.length);
    }

    /**
     * Returns the {@code index}th component of this vector.
     * 
     * @param index the component index.
     * @return the value of the {@code index}th component.
     */
    public E get(int index) {
        return components[index];
    }

    /**
     * Sets the value of the {@code index}th vector component to the given 
     * value. 
     * 
     * @param index the index of the target vector component.
     * @param value the value to set.
     */
    public void set(int index, E value) {
        components[index] = value;
    }

    /**
     * Returns the number of components in this vector.
     * 
     * @return the number of components in this vector.
     */
    public int getNumberOfDimensions() {
        return components.length;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("<");
        String separator = "";

        for (E component : components) {
            stringBuilder.append(separator);
            separator = ", ";
            stringBuilder.append(component);
        }
        return stringBuilder.append(">").toString();
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(components);
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }

        if (o == this) {
            return true;
        }

        if (!o.getClass().equals(this.getClass())) {
            return false;
        }

        Vector<E> other = (Vector<E>) o;
        return Arrays.equals(components, other.components);
    }
}

net.coderodde.math.impl.ComplexNumber

package net.coderodde.math.impl;

/**
 * This class implements a complex number. The complex number consists of a real
 * part and an imaginary part. The imaginary part is a real number equipped with
 * the imaginary unit {@code i}, for which {@code i^2 = -1}. This class is
 * immutable.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class ComplexNumber {

    /**
     * The real number.
     */
    private final double realPart;

    /**
     * The imaginary number.
     */
    private final double imaginaryPart;

    /**
     * Constructs a new complex number.
     * 
     * @param realPart      the real part of the newly constructed complex 
     *                      number.
     * @param imaginaryPart the imaginary part of the newly constructed complex
     *                      number.
     */
    public ComplexNumber(final double realPart, final double imaginaryPart) {
        checkNotNan(realPart);
        checkNotNan(imaginaryPart);
        checkNotInfinite(realPart);
        checkNotInfinite(imaginaryPart);
        this.realPart = realPart;
        this.imaginaryPart = imaginaryPart;
    }

    /**
     * Returns the real part of this complex number.
     * 
     * @return the real part of this complex number.
     */
    public double getRealPart() {
        return realPart;
    }

    /**
     * Returns the imaginary part of this complex number.
     * 
     * @return the imaginary part of this complex number.
     */
    public double getImaginaryPart() {
        return imaginaryPart;
    }

    /**
     * Returns the complex number that is equal to the sum of this complex 
     * number and the {@code other} complex number.
     * 
     * @param other the complex number to add.
     * @return the sum of this and {@code other} complex number.
     */
    public ComplexNumber add(ComplexNumber other) {
        return new ComplexNumber(realPart + other.realPart, 
                                 imaginaryPart + other.imaginaryPart);
    }

    /**
     * Returns the negative of this complex number.
     * 
     * @return the negative of this complex number. 
     */
    public ComplexNumber negate() {
        return new ComplexNumber(-realPart, -imaginaryPart);
    }

    /**
     * Returns the complex number representing the product of the two input 
     * complex numbers.
     * 
     * @param a the first complex number.
     * @param b the second complex number.
     * @return the product of {@code a} and {@code b}.
     */
    public ComplexNumber multiply(ComplexNumber complexNumber) {
        double a = realPart;
        double b = imaginaryPart;
        double c = complexNumber.realPart;
        double d = complexNumber.imaginaryPart;
        double resultRealPart = a * c - b * d;
        double resultImaginaryPart = a * d + b * c;
        return new ComplexNumber(resultRealPart, resultImaginaryPart);
    }

    /**
     * Returns a simple textual representation of this complex number.
     * 
     * @return the textual representation of this complex number.
     */
    @Override
    public String toString() {
        if (realPart == 0.0 && imaginaryPart == 0.0) {
            return "0.0";
        }

        if (realPart == 0.0) {
            return imaginaryPart + "i";
        }

        if (imaginaryPart == 0.0) {
            return Double.toString(realPart);
        }

        if (imaginaryPart < 0.0) {
            return realPart + " - " + Math.abs(imaginaryPart) + "i";
        }

        return realPart + " + " + imaginaryPart + "i";
    }

    /**
     * Checks that the input {@code double} value is not {@code NaN}.
     * 
     * @param d the value to check.
     * @throws IllegalArgumentException in case {@code d} is {@code NaN}.
     */
    private void checkNotNan(double d) {
        if (Double.isNaN(d)) {
            throw new IllegalArgumentException("NaN");
        }
    }

    /**
     * Checks that the input {@code double} value is finite.
     * 
     * @param d the value to check.
     * @throws IllegalArgumentException in case {@code d} is not finite.
     */
    private void checkNotInfinite(double d) {
        if (Double.isInfinite(d)) {
            throw new IllegalArgumentException("Infinite");
        }
    }
}

net.coderodde.math.impl.ComplexVectorAdditive

package net.coderodde.math.impl;

import net.coderodde.math.Additive;
import net.coderodde.math.Vector;

/**
 * This class implements the addition operation over complex vectors.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6:P (May 18, 2019)
 */
public final class ComplexVectorAdditive 
        implements Additive<Vector<ComplexNumber>,
                            Vector<ComplexNumber>,
                            Vector<ComplexNumber>> {

    /**
     * Adds the complex vectors {@code a} and {@code b} and returns the 
     * component-wise copy of the object. Both input complex vectors remain
     * intact.
     * 
     * @param a the left summation operand.
     * @param b the right summation operand.
     * @return the sum vector.
     */
    @Override
    public Vector<ComplexNumber> add(Vector<ComplexNumber> a, 
                                     Vector<ComplexNumber> b) {
        ComplexNumber[] complexNumbers = 
                new ComplexNumber[a.getNumberOfDimensions()];

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            complexNumbers[i] = a.get(i).add(b.get(i));
        }

        return new Vector<>(complexNumbers);
    }
}

net.coderodde.math.impl.ComplexVectorDivisible

package net.coderodde.math.impl;

import net.coderodde.math.Divisible;

/**
 * This class implements the division operator over complex numbers.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class ComplexVectorDivisible implements Divisible<ComplexNumber,
                                                               ComplexNumber,
                                                               ComplexNumber> {

    /**
     * Divides the complex {@code divident} by the complex {@code divisor} and 
     * returns the fraction. Both the input complex numbers remain intact.
     * 
     * @param divident the complex divident.
     * @param divisor  the complex divisor.
     * @return the fraction after dividing the divident by the divisor.
     */
    @Override
    public ComplexNumber divide(ComplexNumber divident, ComplexNumber divisor) {
        // TODO: could do Karatsuba multiplication here, I guess.
        double a = divident.getRealPart();
        double b = divident.getImaginaryPart();
        double c = divisor.getRealPart();
        double d = divisor.getImaginaryPart();

        double resultRealPart = (a * c + b * d) / (c * c + d * d);
        double resultImaginaryPart = (b * c - a * d) / (c * c + d * d);

        return new ComplexNumber(resultRealPart, resultImaginaryPart);
    }
}

net.coderodde.math.impl.ComplexVectorInnerProduct

package net.coderodde.math.impl;

import net.coderodde.math.InnerProduct;
import net.coderodde.math.Vector;

/**
 * This class implements computing inner product over complex vectors.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class ComplexVectorInnerProduct 
        implements InnerProduct<ComplexNumber, ComplexNumber, ComplexNumber> {

    /**
     * Computes the inner product of {@code a} and {@code b} and returns it to
     * the caller.
     * 
     * @param a the first operand.
     * @param b the second operand.
     * @return the inner product.
     */
    @Override
    public ComplexNumber innerProductOf(Vector<ComplexNumber> a,//1 -2i
                                        Vector<ComplexNumber> b) {//1 -2i
        ComplexNumber innerProduct = new ComplexNumber(0.0, 0.0);

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            ComplexNumber complexNumber1 = a.get(i);
            ComplexNumber complexNumber2 = b.get(i);
            ComplexNumber product = complexNumber1.multiply(complexNumber2);
            innerProduct = innerProduct.add(product);
        }

        return innerProduct;
    }
}

net.coderodde.math.impl.ComplexVectorNegative

package net.coderodde.math.impl;

import net.coderodde.math.Negative;
import net.coderodde.math.Vector;

/**
 * This class implements the negation operation over complex numbers.
 * 
 * @author Rodino "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class ComplexVectorNegative 
        implements Negative<Vector<ComplexNumber>,
                            Vector<ComplexNumber>> {

    /**
     * Negates every component in {@code element} and returns the resulting 
     * vector. The input vector remains intact.
     * 
     * @param element the element to negate.
     * @return the element with all the components negated compared to the 
     *         input vector. 
     */
    @Override
    public Vector<ComplexNumber> negate(Vector<ComplexNumber> element) {
        Vector<ComplexNumber> result = new Vector<>(element);

        for (int i = 0; i < element.getNumberOfDimensions(); i++) {
            result.set(i, result.get(i).negate());
        }

        return result;
    }
}

net.coderodde.math.impl.ComplexVectorProductByScalar

package net.coderodde.math.impl;

import net.coderodde.math.Product;
import net.coderodde.math.Vector;

/**
 * This class implements multiplying complex vectors by a complex scalar.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class ComplexVectorProductByScalar 
        implements Product<ComplexNumber, 
                           Vector<ComplexNumber>, 
                           Vector<ComplexNumber>>{

    /**
     * Multiplies the complex vector by the given complex scalar and returns the
     * result. All the input objects remain intact.
     * 
     * @param scalar the scalar to multiply by.
     * @param vector the complex vector to multiply.
     * @return the {@code vector} multiplied by {@code scalar}.
     */
    @Override
    public Vector<ComplexNumber> multiply(ComplexNumber scalar, 
                                          Vector<ComplexNumber> vector) {
        Vector<ComplexNumber> ret = new Vector<>(vector);

        for (int i = 0; i < vector.getNumberOfDimensions(); i++) {
            ret.set(i, ret.get(i).multiply(scalar));
        }

        return ret;
    }
}

net.coderodde.math.impl.RealVectorAdditive

package net.coderodde.math.impl;

import net.coderodde.math.Additive;
import net.coderodde.math.Vector;

/**
 * This class implements addition over {@code double}-valued vectors of an
 * Euclidean space.
 * 
 * @author Rodion "rodde" Efremov 
 * @version 1.6 (May 17, 2019)
 */
public final class RealVectorAdditive implements Additive<Vector<Double>,
                                                          Vector<Double>,
                                                          Vector<Double>> {

    /**
     * Adds component-wise the contents in {@code a} and {@code b} and returns 
     * the sum. Both input vectors remain intact.
     * 
     * @param a the first operand.
     * @param b the second operand.
     * @return the sum of the two input operands.
     */
    @Override
    public Vector<Double> add(Vector<Double> a, Vector<Double> b) {
        Vector<Double> result = new Vector<>(a);

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            result.set(i, result.get(i) + b.get(i));
        }

        return result;
    }
}

net.coderodde.math.impl.RealVectorDivisible

package net.coderodde.math.impl;

import net.coderodde.math.Divisible;

/**
 * This class implements the division of {@code double} values.
 * 
 * @author Rodion  "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public final class RealVectorDivisible 
        implements Divisible<Double, Double, Double> {

    /**
     * Returns the fraction of {@code divident} and {@code divisor}.
     * 
     * @param divident the divident {@code double} value.
     * @param divisor  the divisor {@code double} value.
     * @return the fraction.
     */
    @Override
    public Double divide(Double divident, Double divisor) {
        return divident / divisor;
    }
}

net.coderodde.math.impl.RealVectorInnerProduct

package net.coderodde.math.impl;

import net.coderodde.math.InnerProduct;
import net.coderodde.math.Vector;

/**
 * This class is responsible for computing inner products over real-valued 
 * vectors.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public final class RealVectorInnerProduct 
        implements InnerProduct<Double, Double, Double> {

    /**
     * Computes and returns the inner product of the vectors {@code a} and 
     * {@code b}.
     * 
     * @param a the left operand vector.
     * @param b the right operand vector.
     * @return the inner product of the vectors {@code a} and {@code b}.
     */
    @Override
    public Double innerProductOf(Vector<Double> a, Vector<Double> b) {
        double innerProduct = 0.0;

        for (int i = 0; i < a.getNumberOfDimensions(); i++) {
            innerProduct += a.get(i) * b.get(i);
        }

        return innerProduct;
    }
}

net.coderodde.math.impl.RealVectorNegative

package net.coderodde.math.impl;

import net.coderodde.math.Negative;
import net.coderodde.math.Vector;

/**
 * This class implements negation operation over real vectors.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 17, 2019)
 */
public final class RealVectorNegative implements Negative<Vector<Double>,
                                                          Vector<Double>> {

    /**
     * Negates the input {@code double} vector. The input vector remains intact.
     * 
     * @param a the {@code double} vector to negate.
     * @return the negative of {@code a}.
     */
    @Override
    public Vector<Double> negate(Vector<Double> a) {
        Vector<Double> result = new Vector<>(a);

        for (int i = 0; i < result.getNumberOfDimensions(); i++) {
            result.set(i, -result.get(i));
        }

        return result;
    }

}

net.coderodde.math.impl.RealVectorProductByScalar

package net.coderodde.math.impl;

import net.coderodde.math.Product;
import net.coderodde.math.Vector;

/**
 * This class implements the operation of multiplying a vector by a scalar.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 18, 2019)
 */
public final class RealVectorProductByScalar 
        implements Product<Double, Vector<Double>, Vector<Double>> {

    /**
     * This method multiplies the input vector {@code vector} component-wise by
     * the {@code double} scalar and returns the result. The input vector 
     * remains intact.
     * 
     * @param scalar the scalar.
     * @param vector the vector to multiply by the scalar.
     * @return the input vector multiplied by the input scalar.
     */
    @Override
    public Vector<Double> multiply(Double scalar, Vector<Double> vector) {
        Vector<Double> x = new Vector<>(vector);

        for (int i = 0; i < vector.getNumberOfDimensions(); i++) {
            x.set(i, x.get(i) * scalar);
        }

        return x;
    }
}

net.coderodde.math.GramSchmidtProcessTest

package net.coderodde.math;

import net.coderodde.math.impl.RealVectorAdditive;
import net.coderodde.math.impl.RealVectorDivisible;
import net.coderodde.math.impl.RealVectorInnerProduct;
import net.coderodde.math.impl.RealVectorNegative;
import net.coderodde.math.impl.RealVectorProductByScalar;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;

public class GramSchmidtProcessTest {

    private final GramSchmidtProcess<Double, Double, Double> process = 
            new GramSchmidtProcess<>(new RealVectorInnerProduct(),
                                     new RealVectorDivisible(),
                                     new RealVectorProductByScalar(),
                                     new RealVectorAdditive(),
                                     new RealVectorNegative());

    @Test(expected = NullPointerException.class) 
    public void testThrowsNullPointerExceptionOnNullBasis() {
        process.process(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testThrowsIllegalArgumentExceptionOnNoVectors() {
        process.process();
    }

    @Test
    public void testReturnsSingleVectorWhenBasisContainsOnlyOneVector() {
        Vector<Double> vec = new Vector<>(1.0, 2.2, 3.0);
        Vector<Double>[] result = process.process(vec);
        assertEquals(1, result.length);
        assertEquals(vec, result[0]);
    }

    @Test(expected = IllegalArgumentException.class) 
    public void
         testThrowsIllegalArgumentExceptionWhenFirstVectorHasDimensionZero() {
        Vector<Double> v1 = new Vector<>();
        Vector<Double> v2 = new Vector<>(1.0);
        process.process(v1, v2);
    }

    @Test(expected = IllegalArgumentException.class) 
    public void 
        testThrowsIllegalArgumentExceptionWhenAnotherVectorHasDimensionZero() {
        Vector<Double> v1 = new Vector<>(1.0);
        Vector<Double> v2 = new Vector<>();
        process.process(v1, v2);
    }

    @Test(expected = IllegalArgumentException.class) 
    public void testThrowsIllegalArgumentExceptionWhenDimensionalityMismatch() {
        Vector<Double> v1 = new Vector<>(1.0);
        Vector<Double> v2 = new Vector<>(2.0, 3.0);
        process.process(v1, v2);
    }

    @Test
    public void testValidInput1() {
        Vector<Double> v1 = new Vector<>(1., 1., 1.);
        Vector<Double> v2 = new Vector<>(1., 0., 1.);
        Vector<Double> v3 = new Vector<>(3., 2., 3.);
        Vector<Double>[] orthogonalBasis = process.process(v1, v2, v3);
        assertTrue(Demo.basisIsOrthogonal(orthogonalBasis, 0.001));
    }
}

(The entire project is here.)

Critique request

As always, please tell me anything that comes to mind!

\$\endgroup\$
5
\$\begingroup\$

The way the problem is decomposed doesn't feel right. In particular, there are too many interfaces, and Additive, Divisible, Negative are unnecessarily disconnected.

I recommend to follow a more (mathematically) natural path. The Gram-Schmidt process works in any inner product space (which is by definition a vector space equipped with an inner product), so consider an

    abstract class InnerProductSpace <AbelianGroup<V>, Field<F>> {
        V scale(V vector, F scalar);
        F innerProduct(V v1, V v2);
        V[] orthogonalize(V[] basis) {
            // your Gram-Schmidt implementation here
        }
    }

As a side note, I wouldn't call an orthogonalization method GramShmidt. As a client of this library I am not concerned with which process is used. The only thing I care about is that there is the method taking a basis and returning an orthogonalized one.

I also took a liberty to make a shortcut and not spell out the VectorSpace interface, to which a scale method really belongs.

The Field is what holds addition and multiplication together:

    public interface Field<F> {
        F add(F f1, F f2);
        F mul(F f1, F f2);
        F neg(F f);
        F inv(F f);
   }

It is OK to have sub and div instead of neg and inv.

Notice that the field must be closed under its operation. An addition (or multiplication) returning a type different than the type of arguments makes no mathematical sense.

I have to admit that I have no idea how to express other constraints a.k.a. field axioms. I doubt that it is possible.

\$\endgroup\$
3
\$\begingroup\$

My Linear Algebra is a bit rusty, but I think that your terminology is a bit off:

public class GramSchmidtProcess<VCT, IPT, FT> {
    …

    /**
     * Performs the Gram-Schmidt process upon {@code basis}.
     * 
     * @param basis the basis to process.
     * @return the orthogonal basis.
     */
    public Vector<VCT>[] process(Vector<VCT>... basis) {
        …

        // Remove the duplicates and return whatever is left:
        return removeDuplicates(orthogonalBasis);
    }
}

If the input is in fact a basis, then the vectors are, by definition, linearly independent and spanning. If the inputs are linearly independent, how would it be possible to produce duplicate vectors in the output?

The Wikipedia article says:

If the Gram–Schmidt process is applied to a linearly dependent sequence, it outputs the 0 vector on the ith step, assuming that vi is a linear combination of v1, …, vi−1. If an orthonormal basis is to be produced, then the algorithm should test for zero vectors in the output and discard them because no multiple of a zero vector can have a length of 1.

Perhaps you are prepared to accept as input a list of vectors that do not necessarily constitute a basis? In that case, the basis parameter should be renamed to something more general, such as vectors.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.