МарияБорисовна » 19 сен 2013, 23:38
Naeel Maqsudov писал(а):Нужен алгоритм преобразования разреженной (относительно много нулей) матрицы к блочно-диагональному виду, чтобы все ненулевые элементы "прилипли" к главной диагонали, а нули вытеснились соответственно в 2 угла.
Преобразование должно выполняться перестрановками строк и столбцов, и линейными преобразованиями строк. (Т.е. можно умножить строку на коэффициент и сложить с другой строкой)
Наверняка есть уже готовый велосипед!
1) Начнем с первой строки искать первый ненулевой элемент и обозначим эту сточку (1). После того, как нашелся первый ненулевой элемент, столбец, в котором он находится тоже обозначим (1) и уже в нем ищем ненулевые элементы.
Если такой есть, то строчку в которой он находится(этот ненулевой элемент) так же обозначаем (1). Затем дальше просматриваем исходную строчку и повторяем такие действия до ее конца.
2) Затем смотрим, есть ли у нас строчки, которые мы еще не рассмотрели. Если такие есть, то наивысшую из них обозначаем за (2) и повторяем алгоритм, описанный выше.
Все это следует повторять, пока не будут просмотрены все строки и столбцы.
3) Итак, все строки обозначены. Теперь переставляем строки так, чтобы их обозначения были в порядке возрастания. То есть, сначала идут строчки под номером (1), потом под номером (2) и т.д.
4) Переставляем столбцы по тому же принципу.
Получаем матрицу а исходную, приведенную к блочно-диагональному виду.
[quote="Naeel Maqsudov"]Нужен алгоритм преобразования разреженной (относительно много нулей) матрицы к блочно-диагональному виду, чтобы все ненулевые элементы "прилипли" к главной диагонали, а нули вытеснились соответственно в 2 угла.
Преобразование должно выполняться перестрановками строк и столбцов, и линейными преобразованиями строк. (Т.е. можно умножить строку на коэффициент и сложить с другой строкой)
Наверняка есть уже готовый велосипед![/quote]
1) Начнем с первой строки искать первый ненулевой элемент и обозначим эту сточку (1). После того, как нашелся первый ненулевой элемент, столбец, в котором он находится тоже обозначим (1) и уже в нем ищем ненулевые элементы.
Если такой есть, то строчку в которой он находится(этот ненулевой элемент) так же обозначаем (1). Затем дальше просматриваем исходную строчку и повторяем такие действия до ее конца.
2) Затем смотрим, есть ли у нас строчки, которые мы еще не рассмотрели. Если такие есть, то наивысшую из них обозначаем за (2) и повторяем алгоритм, описанный выше.
Все это следует повторять, пока не будут просмотрены все строки и столбцы.
3) Итак, все строки обозначены. Теперь переставляем строки так, чтобы их обозначения были в порядке возрастания. То есть, сначала идут строчки под номером (1), потом под номером (2) и т.д.
4) Переставляем столбцы по тому же принципу.
Получаем матрицу а исходную, приведенную к блочно-диагональному виду.