Generic Strassen Matrix Multiplication

Použití

Lorem ipsum

Dokumentace & Licence

Licence

Lorem ipsum

Dokumentace

Rozhrani Entry reprezentuje objekt se kterym lze delat matematicke operace scitani/nasobeni/odcitani.

interface Entry < E >
{
  E times ( E entry ) ;
  E plus ( E entry ) ;
  E minus ( E entry ) ;
}

Rozhrani Matrix reprezentuje ctvercovou matici, jejiz rozmer je mocnina dvojky.

interface Matrix < E > extends Entry < Matrix < E > >
{
    // Vrati rozmer matice.
    int getSize();
    // Vrati prvek na indexu n, m (1 <= n <= getSize(), 1 <= m <= getSize()).
    E getElement(int n, int m);
    // Vrati levou horni podmatici.
    Matrix<E> getTopLeftSubmatrix();
    // Vrati pravou horni podmatici.
    public Matrix<E> getTopRightSubmatrix();
    // Vrati levou dolni podmatici.
    public Matrix<E> getBottomLeftSubmatrix();
    // Vrati pravou dolni podmatici.
    public Matrix<E> getBottomRightSubmatrix();
    // Vrati soucet matic this a other
    public Matrix<E> plus(Matrix<E> other);
    // Vrati rozdil matic this a other
    public Matrix<E> minus(Matrix<E> other);
    // Vrati soucin matic this a other
    public Matrix<E> times(Matrix<E> other);
}

Kód

class GenericMatrix < E extends Entry < E > > implements Matrix < E >
{

  ///////////////////////////////////////////////////////////////

  private Matrix < E > top_left = null;
  private Matrix < E > top_right = null;
  private Matrix < E > bottom_left = null;
  private Matrix < E > bottom_right = null;

  ///////////////////////////////////////////////////////////////

  private int size;
  private int center;
  private E value;

  ///////////////////////////////////////////////////////////////

  public GenericMatrix ( E [][] contents )
  {

    if( contents==null ) return;
    size = contents.length;
    center = size/2;

    if( contents.length==1 )
    {
      value = contents[0][0];
      top_left     = this;
      top_right    = this;
      bottom_left  = this;
      bottom_right = this;
      return;
     }

     E[][] A11 = (E[][]) new Object[center][center];

     for(int i=0; i<center ; i++)
       for(int j=0; j<center ; j++)
         A11[i][j]=contents[i][j];

     E[][] A12 = (E[][]) new Object[center][center];

     for(int i=0; i<center ; i++)
       for(int j=center; j<size ; j++)
         A12[i][j-center]=contents[i][j];

     E[][] A21 = (E[][]) new Object[center][center];

     for(int i=center; i<size ; i++)
       for(int j=0; j<center ; j++)
         A21[i-center][j]=contents[i][j];

     E[][] A22 = (E[][]) new Object[center][center];

     for(int i=center; i<size ; i++)
       for(int j=center; j<size ; j++)
         A22[i-center][j-center]=contents[i][j];

     top_left     =  new GenericMatrix<E> ( A11 );
     top_right    =  new GenericMatrix<E> ( A12 );
     bottom_left  =  new GenericMatrix<E> ( A21 );
     bottom_right =  new GenericMatrix<E> ( A22 );

    }

	///////////////////////////////////////////////////////////////

  public E getElement( int y , int x )
  {

    if( size==1 ) return value;

    if(y>center)
    {
      if( x>center )
        return bottom_right.getElement( y-center , x-center );
        return bottom_left.getElement( y-center , x);
    }
    else
    {
      if( x>center )
        return top_right.getElement( y , x-center );
	return top_left.getElement( y , x );
    }

  }

	///////////////////////////////////////////////////////////////

  public int getSize()
  {
    return this.size;
  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> minus(Matrix<E> other)
  {

    E[][] array = (E[][]) new Object[other.getSize()][other.getSize()];

    for(int i=0; i<size ; i++)
      for(int j=0; j<size; j++)
        array[i][j] = this.getElement(i+1,j+1).minus(other.getElement(i+1, j+1));

    return new GenericMatrix<E>(array);

  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> plus(Matrix<E> other)
  {

    E[][] array = (E[][]) new Object[other.getSize()][other.getSize()];

    for(int i=0; i<size ; i++)
      for(int j=0; j<size; j++)
        array[i][j] = this.getElement(i+1,j+1).plus(other.getElement(i+1, j+1));

    return new GenericMatrix<E>(array);

  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> times(Matrix<E> other)
  {

    E [][] result = (E[][]) new Object[other.getSize()][other.getSize()];	

    if(this.getSize() == 1)
    {
      result[0][0] = this.getElement(0,0).times(other.getElement(0,0));
      return new GenericMatrix<E>(result);
    }

    Matrix<E> A11 = this.getTopLeftSubmatrix();
    Matrix<E> A12 = this.getTopRightSubmatrix();
    Matrix<E> A21 = this.getBottomLeftSubmatrix();
    Matrix<E> A22 = this.getBottomRightSubmatrix();

    Matrix<E> B11 = other.getTopLeftSubmatrix();
    Matrix<E> B12 = other.getTopRightSubmatrix();
    Matrix<E> B21 = other.getBottomLeftSubmatrix();
    Matrix<E> B22 = other.getBottomRightSubmatrix();

    Matrix<E> P1 = (A11.plus(A22)).times(B11.plus(B22));
    Matrix<E> P2 = (A21.plus(A22)).times(B11);
    Matrix<E> P3 = A11.times(B12.minus(B22));
    Matrix<E> P4 = A22.times(B21.minus(B11));
    Matrix<E> P5 = (A11.plus(A12)).times(B22);
    Matrix<E> P6 = (A21.minus(A11)).times(B11.plus(B12));
    Matrix<E> P7 = (A12.minus(A22)).times(B21.plus(B22));

    Matrix<E> C11 = P7.plus((P1.plus(P4)).minus(P5));
    Matrix<E> C12 = P3.plus(P5);
    Matrix<E> C21 = P2.plus(P4);
    Matrix<E> C22 = ((P1.plus(P3)).minus(P2)).plus(P6);

    GenericMatrix<E> res = new GenericMatrix<E>(result);
    res.putTree(C11,C12,C21,C22);
    return res;

  }

	///////////////////////////////////////////////////////////////

  private void putTree(Matrix<E> C11, Matrix<E> C12, Matrix<E> C21, Matrix<E> C22)
  {
    this.top_left=C11;
    this.top_right=C12;
    this.bottom_left=C21;
    this.bottom_right=C22;

  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> getBottomLeftSubmatrix()
  {
    return bottom_left;
  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> getBottomRightSubmatrix()
  {
    return bottom_right;
  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> getTopLeftSubmatrix()
  {
    return top_left;
  }

	///////////////////////////////////////////////////////////////

  public Matrix<E> getTopRightSubmatrix()
  {
    return top_right;
  }

	///////////////////////////////////////////////////////////////

}

Download