DAS_2023_1/martysheva_tamara_lab_6

Лабораторная работа №6 - Параллельный поиск значения детерминанта матрицы

Кратко: реализовать нахождение детерминанта квадратной матрицы.

Подробно: в лабораторной работе требуется сделать два алгоритма: обычный и параллельный. В параллельном алгоритме предусмотреть ручное задание количества потоков, каждый из которых будет выполнять нахождение отдельной группы множителей.

---

Ход работы:

Обычный алгоритм SequentialDeterminant:

    public static int SequentialDeterminant(int[][] matrix, int size) {
        if (size == 1) {
            return matrix[0][0];
        }
        else if (size == 2) {
            return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        }
        else {
            int det = 0;
            for (int i = 0; i < size; i++) {
                var submatrix = Submatrix(matrix, i);
                det += Math.pow(-1, i) * matrix[0][i] * SequentialDeterminant(submatrix, submatrix.length);
            }
            return det;
        }
    }

Если матрица имеет размер более 2х2, то вычисление определителя происходит с рекурсивным вызовом с использованием миноров:

    private static int[][] Submatrix(int[][] matrix, int excludeCol) {
        int size = matrix.length - 1;
        int[][] submatrix = new int[size][size];

        int rowIndex = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (i == 0) {
                continue;
            }
            int colIndex = 0;
            for (int j = 0; j < matrix[i].length; j++) {
                if (j == excludeCol) {
                    continue;
                }
                submatrix[rowIndex][colIndex] = matrix[i][j];
                colIndex++;
            }
            rowIndex++;
        }
        return submatrix;
    }

Метод создает подматрицу матрицы, исключая указанный столбец.

Параллельный алгоритм ParallelDeterminant:

    public static int ParallelDeterminant(int[][] matrix, int size, int threads) {
        if (size == 1) {
            return matrix[0][0];
        }
        else if (size == 2) {
            return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        }
        else {
            int det = 0;
            ExecutorService executor = Executors.newFixedThreadPool(threads);
            List<Callable<Integer>> tasks = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                var submatrix = Submatrix(matrix, i);
                int finalI = i;
                tasks.add(() -> (int) Math.pow(-1, finalI) * matrix[0][finalI] * SequentialDeterminant(submatrix, submatrix.length));
            }

            try {
                List<Future<Integer>> futures = executor.invokeAll(tasks);
                for (Future<Integer> future : futures) {
                    det += future.get();
                }
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
                return -1;
            } finally {
                executor.shutdown();
            }

            return det;
        }
    }

Создается исполнительский сервис (ExecutorService) с фиксированным числом потоков. Создается список задач (tasks), где каждая задача представляет собой вычисление минора для соответствующего столбца. После запуска задач в пуле потоков, ожидаем завершения выполнения. Далее формируется конечный результат.

Результат

На больших матрицах алгоритм работает очень долго*

• На матрице 6x6 последовательный алгоритм справился намного быстрее параллельного.
• На матрице 9x9 уже параллельный алгоритм справляется быстрее.
• На матрице 12x12 параллельный алгоритм тоже лидирует.