Участник:Zerika

Седловой элемент матрицы [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:

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

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

Для матрицы размером 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 также может выполняться параллельно.
• Параллельная сложность:

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

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

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

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

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

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

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