Умножение матрицы «разделяй и властвуй»

Question

У меня проблемы с получением умножения матрицы «разделяй и властвуй». Из того, что я понимаю, вы разбиваете матрицы размера nxn на квадранты (каждый квадрант равен n / 2) и затем делаете:

C11 = A11⋅ B11 + A12 ⋅ B21   
C12 = A11⋅ B12 + A12 ⋅ B22  
C21 = A21 ⋅ B11 + A22 ⋅ B21  
C22 = A21 ⋅ B12 + A22 ⋅ B22  

Мои результаты «разделяй и властвуй» действительно велики, и у меня возникают проблемы с выяснением проблемы, поскольку я не очень хорош в рекурсии

пример вывода:

Оригинальная матрица A:

4 0 4 3   
5 4 0 4   
4 0 4 0  
4 1 1 1 

A x A

Классический:

44 3 35 15  
56 20 24 35  
32 0 32 12  
29 5 21 17  

Разделяй и властвуй:

992 24 632 408  
1600 272 720 1232   
512 0 512 384  
460 17 405 497  

Может ли кто-нибудь сказать мне, что я делаю неправильно для разделения и завоевания? Все мои матрицы int[][], а классический метод - это традиционные 3 для умножения циклических матриц

Answer 1

Вы рекурсивно вызываете divideAndConquer неверным способом. То, что делает ваша функция, это квадрат матрицы. Чтобы умножение матрицы «разделяй и властвуй» работало, необходимо уметь умножать две потенциально разные матрицы вместе.

Это должно выглядеть примерно так:

private static int[][] divideAndConquer(int[][] matrixA, int[][] matrixB){
    if (matrixA.length == 2){
         //calculate and return base case
    }
    else {
        //make a11, b11, a12, b12 etc. by dividing a and b into quarters      
        int[][] c11 = addMatrix(divideAndConquer(a11,b11),divideAndConquer(a12,b21));
        int[][] c12 = addMatrix(divideAndConquer(a11,b12),divideAndConquer(a12,b22));
        int[][] c21 = addMatrix(divideAndConquer(a21,b11),divideAndConquer(a22,b21));
        int[][] c22 = addMatrix(divideAndConquer(a21,b12),divideAndConquer(a22,b22));
        //combine result quarters into one result matrix and return
    }
}

Answer 2

Некоторые подходы к отладке, чтобы попробовать:

• Попробуйте ввести в качестве входных данных несколько очень простых тестовых матриц (например, все нули, с одним или несколькими стратегическими). Вы можете увидеть шаблон в «сбоях», который покажет вам, где находятся ваши ошибки.

• Убедитесь, что ваш «классический» подход дает вам правильные ответы. Для маленьких матриц вы можете использовать Woflram Alpha для проверки ответов: http://www.wolframalpha.com/examples/Matrices.html

• Для отладки рекурсии: добавьте операторы printf() на входе и выходе из вашей функции, включая аргументы вызова. Запустите тестовую матрицу, запишите вывод в файл журнала и откройте файл журнала в текстовом редакторе. Пройдитесь по каждому делу, напишите свои заметки в редакторе и убедитесь, что он работает правильно на каждом этапе. Добавьте еще printf() операторов и, при необходимости, запустите снова.

Удачи с домашним заданием!

Answer 3

Может кто-нибудь сказать мне, что я делаю неправильно для разделения и завоевания?

Да:

   int[][] a = divideAndConquer(topLeft);
   int[][] b = divideAndConquer(topRight);
   int[][] c = divideAndConquer(bottomLeft);
   int[][] d = divideAndConquer(bottomRight);

   int[][] c11 = addMatrix(classical(a,a),classical(b,c));
   int[][] c12 = addMatrix(classical(a,b),classical(b,d));
   int[][] c21 = addMatrix(classical(c,a),classical(d,c));
   int[][] c22 = addMatrix(classical(c,b),classical(d,d));

Вы проходите здесь дополнительный шаг умножения:Вы не должны звонить как divideAndConquer(), так и classical().

. То, что вы эффективно делаете, это:

C11 = (A11^2)⋅(B11^2) + (A12^2)⋅(B21^2)
C12 = (A11^2)⋅(B12^2) + (A12^2)⋅(B22^2)
C21 = (A21^2)⋅(B11^2) + (A22^2)⋅(B21^2)
C22 = (A21^2)⋅(B12^2) + (A22^2)⋅(B22^2)

, что неверно.

1. Сначала удалите вызовы divideAndConquer() и замените a / b / c / d на topLeft / topRight / etc.Посмотрите, дает ли он правильные результаты.

2. Вашему методу divideAndConquer() требуется пара входных параметров, поэтому вы можете использовать A * B.Как только вы это заработаете, избавьтесь от вызовов на classical() и используйте вместо этого divideAndConquer().(или сохраните их для матриц, не кратных длине 2).

Answer 4

Может оказаться полезной статья в вики о алгоритме Штрассена .