자바 가 쓴 행렬 곱셈 인 스 턴 스(Strassen 알고리즘)를 사용 합 니 다.

Strassen 알고리즘 은 1969 년 에 독일 수학자 Strassen 이 제기 한 것 으로 이 방법 은 7 개의 중간 변 수 를 도입 하고 모든 중간 변 수 는 한 번 의 곱셈 연산 만 해 야 한다.소박 한 알고리즘 은 8 번 의 곱셈 연산 이 필요 하 다.
의 원리
Strassen 알고리즘 의 원 리 는 다음 과 같 습 니 다.sympy 를 사용 하여 Strassen 알고리즘 의 정확성 을 검증 합 니 다.

import sympy as s
 
A = s.Symbol("A")
B = s.Symbol("B")
C = s.Symbol("C")
D = s.Symbol("D")
E = s.Symbol("E")
F = s.Symbol("F")
G = s.Symbol("G")
H = s.Symbol("H")
p1 = A * (F - H)
p2 = (A + B) * H
p3 = (C + D) * E
p4 = D * (G - E)
p5 = (A + D) * (E + H)
p6 = (B - D) * (G + H)
p7 = (A - C) * (E + F)
 
print(A * E + B * G, (p5 + p4 - p2 + p6).simplify())
print(A * F + B * H, (p1 + p2).simplify())
print(C * E + D * G, (p3 + p4).simplify())
print(C * F + D * H, (p1 + p5 - p3 - p7).simplify())

복잡 도 분석
$$f(N)=7\times f(\frac{N}{2})=7^2\times f(\frac{N}{4})=...=7^k\times f(\frac{N}{2^k})$$
최종 복잡 도 는$7^{log2 N}=N^{log_2 7}$
자바 매트릭스 곱셈(Strassen 알고리즘)
코드 는 다음 과 같 습 니 다.데이터 구조의 정 의 를 볼 수 있 고 시간 이 공간 을 바 꿀 수 있 습 니 다.

public class Matrix {
	private final Matrix[] _matrixArray;
	private final int n;
	private int element;
	public Matrix(int n) {
		this.n = n;
		if (n != 1) {
			this._matrixArray = new Matrix[4];
			for (int i = 0; i < 4; i++) {
				this._matrixArray[i] = new Matrix(n / 2);
			}
		} else {
			this._matrixArray = null; 
		}
	}
	private Matrix(int n, boolean needInit) {
		this.n = n;
		if (n != 1) {
			this._matrixArray = new Matrix[4];
		} else {
			this._matrixArray = null; 
		}
	}
	public void set(int i, int j, int a) {
		if (n == 1) {
			element = a;
		} else {
			int size = n / 2;
			this._matrixArray[(i / size) * 2 + (j / size)].set(i % size, j % size, a);
		}
	}
	public Matrix multi(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element * m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = P5(m).add(P4(m)).minus(P2(m)).add(P6(m));
			result._matrixArray[1] = P1(m).add(P2(m));
			result._matrixArray[2] = P3(m).add(P4(m));
			result._matrixArray[3] = P5(m).add(P1(m)).minus(P3(m)).minus(P7(m));
		}
		return result;
	}
	public Matrix add(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element + m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = this._matrixArray[0].add(m._matrixArray[0]);
			result._matrixArray[1] = this._matrixArray[1].add(m._matrixArray[1]);
			result._matrixArray[2] = this._matrixArray[2].add(m._matrixArray[2]);
			result._matrixArray[3] = this._matrixArray[3].add(m._matrixArray[3]);;
		}
		return result;
	}
	public Matrix minus(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element - m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = this._matrixArray[0].minus(m._matrixArray[0]);
			result._matrixArray[1] = this._matrixArray[1].minus(m._matrixArray[1]);
			result._matrixArray[2] = this._matrixArray[2].minus(m._matrixArray[2]);
			result._matrixArray[3] = this._matrixArray[3].minus(m._matrixArray[3]);;
		}
		return result;
	}
	protected Matrix P1(Matrix m) {
		return _matrixArray[0].multi(m._matrixArray[1]).minus(_matrixArray[0].multi(m._matrixArray[3]));
	}
	protected Matrix P2(Matrix m) {
		return _matrixArray[0].multi(m._matrixArray[3]).add(_matrixArray[1].multi(m._matrixArray[3]));
	}
	protected Matrix P3(Matrix m) {
		return _matrixArray[2].multi(m._matrixArray[0]).add(_matrixArray[3].multi(m._matrixArray[0]));
	}
	protected Matrix P4(Matrix m) {
		return _matrixArray[3].multi(m._matrixArray[2]).minus(_matrixArray[3].multi(m._matrixArray[0]));
	}
	protected Matrix P5(Matrix m) {
		return (_matrixArray[0].add(_matrixArray[3])).multi(m._matrixArray[0].add(m._matrixArray[3]));
	}
	protected Matrix P6(Matrix m) {
		return (_matrixArray[1].minus(_matrixArray[3])).multi(m._matrixArray[2].add(m._matrixArray[3]));
	}
	protected Matrix P7(Matrix m) {
		return (_matrixArray[0].minus(_matrixArray[2])).multi(m._matrixArray[0].add(m._matrixArray[1]));
	}
	public int get(int i, int j) {
		if (n == 1) {
			return element;
		} else {
			int size = n / 2;
			return this._matrixArray[(i / size) * 2 + (j / size)].get(i % size, j % size);
		}
	}
	public void display() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(get(i, j));
				System.out.print(" ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Matrix m = new Matrix(2);
		Matrix n = new Matrix(2);
		m.set(0, 0, 1);
		m.set(0, 1, 3);
		m.set(1, 0, 5);
		m.set(1, 1, 7);
		n.set(0, 0, 8);
		n.set(0, 1, 4);
		n.set(1, 0, 6);
		n.set(1, 1, 2);
		Matrix res = m.multi(n);
		res.display();
	}
 
}

총결산
자바 로 쓴 행렬 곱셈 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.자바 행렬 곱셈(Strassen 알고리즘)에 관 한 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!