Участник:Zerika: различия между версиями

Текущая версия от 21:11, 9 декабря 2025

Седловой элемент матрицы [math]\displaystyle{ A = (a_{i, j})_{i = 1, j = 1}^{m, n} }[/math] — элемент матрицы [math]\displaystyle{ a_{k, d} }[/math], удовлетворяющий условиям [math]\displaystyle{ a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j} }[/math], то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что [math]\displaystyle{ a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j} }[/math]. Более того, для матрицы существует седловой элемент тогда и только тогда, когда [math]\displaystyle{ \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j} }[/math]. Примеры
Матрица

[math]\displaystyle{ \begin{bmatrix} 5 & 6 & 4 & 5\\ -2 & 5 & 3 & 7\\ 8 & 7 & -2 & 6\\ \end{bmatrix} }[/math]

имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица

[math]\displaystyle{ \begin{bmatrix} 2 & 3 & 5 & 2\\ 2 & 4 & 6 & 2\\ -2 & 7 & 2 & 0\\ \end{bmatrix} }[/math]

имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.

Свойства и структура алгоритма

Общее описание алгоритма

Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

Алгоритм применяется для решения задач выпукло-вогнутой оптимизации, игр с нулевой суммой, экономики и машиностроения. Входными данными служат функция двух переменных с соответствующими пространствами определения (часто выпуклыми и ограниченными) и дополнительные параметрические сведения (градиенты, Гессианы, при наличии). Выходом является приближённое значение седловой точки.

Математическое описание

Пусть задана матрица A размерности m x n (m строк, n столбцов).

Элемент A_ij является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

A_ij = min A_ik, k от 1 до n

Он является максимальным элементом в своем столбце j:

A_ij = max A_dj, d от 1 до m

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

∀k: A_ij ≤ A_ik и ∀d: A_ij ≥ A_dj

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы A_ij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы A_id соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.

Макроструктура алгоритма

Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

Схема реализации последовательного алгоритма

Для каждой строки i:

Найти индекс позиции j минимального элемента строки.
Проверить, является ли A_i,j максимальным в столбце j.
Если да — вернуть (i,j) как седловую точку.
Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

Последовательная сложность алгоритма

Для матрицы размером m×n
Поиск минимума в строке занимает — O(n)
Проверка максимума в столбце — O(m)
Итого на каждую строку — O(m+n)
Общая сложность — O(m(m+n)), что при квадратной матрице n = m равно O(n^2)

Информационный граф

Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

Ресурс параллелизма алгоритма

Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
Параллельная сложность:

При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.

Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.

Входные и выходные данные алгоритма

Входные данные: Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

Выходные данные: Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

Свойства алгоритма

В матрице может быть несколько седловых точек или ни одной
Алгоритм устойчив к дублирующимся значениям

Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

   def find_all_saddle_points_optimized(matrix):

   if not matrix or not matrix[0]:
       return []
   
   m = len(matrix)  # количество строк
   n = len(matrix[0])  # количество столбцов
   
   saddle_points = []
   
   for i in range(m):
       # Шаг 1: Находим все индексы минимальных элементов в строке i
       min_in_row = matrix[i][0]
       min_indices = [0]
       
       for j in range(1, n):
           if matrix[i][j] < min_in_row:
               min_in_row = matrix[i][j]
               min_indices = [j]
           elif matrix[i][j] == min_in_row:
               min_indices.append(j)
       
       # Шаг 2: Для каждого минимального элемента проверяем,
       # является ли он максимальным в своем столбце
       for j in min_indices:
           is_saddle = True
           for k in range(m):
               if matrix[k][j] > matrix[i][j]:
                   is_saddle = False
                   break
           
           if is_saddle:
               saddle_points.append({
                   'row': i,
                   'col': j,
                   'value': matrix[i][j]
               })
   
   return saddle_points

2.2 Возможные способы и особенности параллельной реализации алгоритма

   def find_all_saddle_points_parallel(matrix):
   if not matrix or not matrix[0]:
       return []
   
   m = len(matrix)
   n = len(matrix[0])
   
   def process_row(i):
       """
       Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
       """
       row_results = []
       
       # Находим все минимальные элементы в строке
       min_in_row = matrix[i][0]
       min_indices = [0]
       
       for j in range(1, n):
           if matrix[i][j] < min_in_row:
               min_in_row = matrix[i][j]
               min_indices = [j]
           elif matrix[i][j] == min_in_row:
               min_indices.append(j)
       
       # Для каждого минимального элемента проверяем условие
       for j in min_indices:
           is_saddle = True
           for k in range(m):
               if matrix[k][j] > matrix[i][j]:
                   is_saddle = False
                   break
           
           if is_saddle:
               row_results.append((i, j, matrix[i][j]))
       
       return row_results
   
   # Параллельная обработка строк
   saddle_points = []
   with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
       futures = [executor.submit(process_row, i) for i in range(m)]
       
       # Собираем все результаты
       for future in concurrent.futures.as_completed(futures):
           row_results = future.result()
           for result in row_results:
               saddle_points.append({
                   'row': result[0],
                   'col': result[1],
                   'value': result[2]
               })
   
   return saddle_points

2.3 Результаты прогонов

Для всех запусков седловая точка не была найдена (No saddle point found). Значения времени усреднены по трём прогонам. Время показано в секундах.

Размер матрицы	1 процесс	2 процесса	4 процесса	8 процессов	16 процессов	32 процесса	64 процесса
1000x1000	0.000358	0.000233	0.000156	0.000079	0.000064	0.000038	0.000015
2000x2000	0.001373	0.000926	0.000701	0.000536	0.000273	0.000090	0.000042
3000x3000	0.003451	0.002439	0.001691	0.001200	0.000617	0.000166	0.000085
4000x4000	0.007259	0.003992	0.002923	0.001972	0.001029	0.000298	0.000135
5000x5000	0.011327	0.006031	0.004380	0.002532	0.001452	0.000439	0.000236
6000x6000	0.016217	0.008659	0.007147	0.003346	0.002009	0.000606	0.000326
7000x7000	0.022054	0.011617	0.008796	0.004212	0.002220	0.000914	0.000399
8000x8000	0.028572	0.015224	0.009939	0.005330	0.002697	0.001254	0.000534
9000x9000	0.035642	0.019085	0.012258	0.006447	0.003769	0.001428	0.000769
10000x10000	0.043867	0.023461	0.012777	0.007889	0.004756	0.002258	0.000792
11000x11000	0.052932	0.028309	0.018155	0.009360	0.005155	0.002243	0.001000

2.4 Выводы для классов архитектур

Сильные стороны для данного алгоритма:

Высокая эффективность для больших матриц

Минимальные накладные расходы на передачу данных (матрица в общей памяти)

Простота реализации

Ограничения:

Масштабируемость ограничена пропускной способностью памяти

Эффективность падает для маленьких задач (37.3% для 1000×1000 на 64 ядрах)

Конкуренция за доступ к памяти при проверке столбцов

Рекомендации:

Использовать для матриц размером ≥5000×5000

2.5 Код на MPI

   #include <stdio.h>
   #include <stdlib.h>
   #include <mpi.h>
   #include <time.h>

   typedef struct {
   int row;
   int col;
   } SaddlePoint;

   int main(int argc, char* argv[])
   {
   int rank, size;
   int m, n;
   int i, j;

   MPI_Init(&argc, &argv);
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
   MPI_Comm_size(MPI_COMM_WORLD, &size);

   if (argc != 3) {
       if (rank == 0) {
           fprintf(stderr, "Usage: %s <rows> <cols>\n", argv[0]);
       }
       MPI_Finalize();
       return 1;
   }

   m = atoi(argv[1]);
   n = atoi(argv[2]);

   if (m <= 0 || n <= 0) {
       if (rank == 0) {
           fprintf(stderr, "Matrix dimensions must be positive.\n");
       }
       MPI_Finalize();
       return 1;
   }

   /* Каждый процесс выделяет память под всю матрицу */
   int* A = (int*)malloc(m * n * sizeof(int));
   if (A == NULL) {
       if (rank == 0) fprintf(stderr, "Memory allocation failed.\n");
       MPI_Abort(MPI_COMM_WORLD, 1);
   }

   /* Процесс 0 генерирует матрицу */
   if (rank == 0) {
       srand((unsigned int)time(NULL));
       for (i = 0; i < m; i++) {
           for (j = 0; j < n; j++) {
               A[i * n + j] = rand() % 1000;
           }
       }
   }

   /* Рассылаем всю матрицу всем процессам */
   MPI_Bcast(A, m * n, MPI_INT, 0, MPI_COMM_WORLD);

   /* === НАЧАЛО ЗАМЕРА ВРЕМЕНИ === */
   MPI_Barrier(MPI_COMM_WORLD);
   double t1 = MPI_Wtime();

   /* Каждый процесс обрабатывает строки: i % size == rank */
   int max_local = (m + size - 1) / size; /* верхняя оценка числа строк на процесс */
   SaddlePoint* local_saddles = (SaddlePoint*)malloc(max_local * sizeof(SaddlePoint));
   int local_count = 0;

   for (i = rank; i < m; i += size) {
       /* Уровень 1: найти минимум в строке i */
       int min_val = A[i * n + 0];
       int min_j = 0;
       for (j = 1; j < n; j++) {
           if (A[i * n + j] < min_val) {
               min_val = A[i * n + j];
               min_j = j;
           }
       }

       /* Уровень 2: проверить максимум в столбце min_j */
       int is_max = 1;
       for (j = 0; j < m; j++) {
           if (A[j * n + min_j] > min_val) {
               is_max = 0;
               break;
           }
       }

       if (is_max) {
           local_saddles[local_count].row = i;
           local_saddles[local_count].col = min_j;
           local_count++;
       }
   }

   double t2 = MPI_Wtime();

   /* Собрать результаты */
   int* all_counts = NULL;
   int total_saddles = 0;

   if (rank == 0) {
       all_counts = (int*)malloc(size * sizeof(int));
   }

   MPI_Gather(&local_count, 1, MPI_INT, all_counts, 1, MPI_INT, 0, MPI_COMM_WORLD);

   if (rank == 0) {
       for (i = 0; i < size; i++) {
           total_saddles += all_counts[i];
       }
   }

   SaddlePoint* global_saddles = NULL;
   int* displs = NULL;

   if (rank == 0) {
       global_saddles = (SaddlePoint*)malloc(total_saddles * sizeof(SaddlePoint));
       displs = (int*)malloc(size * sizeof(int));
       displs[0] = 0;
       for (i = 1; i < size; i++) {
           displs[i] = displs[i - 1] + all_counts[i - 1];
       }
   }

   MPI_Gatherv(
       local_saddles, local_count, MPI_BYTE,
       global_saddles, all_counts, displs, MPI_BYTE,
       0, MPI_COMM_WORLD
   );

   /* Вывод */
   if (rank == 0) {
       FILE* fout = fopen("result.out", "a");
       if (fout) {
           fprintf(fout, "%d %d %.6f\n", m, size, t2 - t1);
           fclose(fout);
       }

       if (total_saddles == 0) {
           printf("No saddle point found.\n");
       } else {
           printf("Found %d saddle point(s):\n", total_saddles);
           for (i = 0; i < total_saddles; i++) {
               printf("  (%d, %d)\n", global_saddles[i].row, global_saddles[i].col);
           }
       }
       printf("Matrix: %dx%d, Processes: %d, Time: %.6f seconds\n", m, n, size, t2 - t1);

       free(all_counts);
       free(displs);
       free(global_saddles);
   }

   free(local_saddles);
   free(A);
   MPI_Finalize();
   return 0;
   }