Быстрое умножение булевых матриц

← →
D-alone (2005-01-18 22:03) [0]

Необходимо перемножить большое число булевых матриц в различных последовательностях. Булева матрица - это матрица из нулей и единиц, где умножение и сложение - логические, размерность 6*6 в моем случае. Всего необходимо обсчитать 2^36 штук матриц. Сейчас моя программа умножает матрицы стандартным способом, что очень медленно (19 дней необходимо). Есть идея но не знаю как реализовать. Идея следующая: каждую матрицу закодировать десятичным числом (построчное выписывание нулей и единиц - получим битовое представление некоторого числа) - т.е. не придется генерировать матрицу, для умножения имеет смысл отдельно разбивать матрицу на строки и столбцы.
можно сделать 2 массива чисел: 1 массив - это строки - это просто число, являющееся кодом, разбитое на блоки по нескольку бит (несколько=размерности), 2 массив - столбцы.0-й бит, нный бит, 2нный бит, 3нный бит и т.д.
Теперь, в цикле, где матрицы перемножаются результат для ячейки [i,j]=строка AND столбец.
Кол-во сдвигов уменьшается с N^3 до N^2
первая (или 0-я) строка
s[0]=M AND (2^n-1)
s[1]=(M SHR n) AND (2^n-1)
s[2]=(M SHR 2n) AND (2^n-1)
и т.д.
со столбцами посложнее
их надо выделять побитово. как не знаю.
лучше бы конечно это на асме накидать, но я в нем уже почти ноль.
Помогите это все как-то нормально оформить буду очень благодарен.

← →
MBo © (2005-01-18 22:14) [1]

Определи, что означает умножение таких матриц.
Например, обычное матричное умножение A*B=C, где Cij=Sum (по к) Aik*Bkj
Что будет в твоем случае?
Приведи пример для матриц 2*2

← →
palva © (2005-01-18 23:34) [2]

Предлагаю хранить матрицу следующим образом: Первые 6 байтов матрица по строкам, т. е. каждая строка в младших битах байта. Следующие 6 байтов матрица по столбцам, т. е. каждый столбец в младших битах байта. Первое представление используется, когда матрица является левым множителем, второе представление - когда правым.

При перемножении никаких сдвигов не будет. Нужно взять AND соответствующих байтов, представляющих строку левой матрицы и столбец правой и сразу после этого проверить флаг четности. Если он установлен, то элемент произведения равен 1, иначе 0. Это надо делать на ассемблере, но тут будет буквально три команды.

← →
palva © (2005-01-18 23:38) [3]

MBo © (18.01.05 22:14) [1]
Это будет как обычное произведение матриц из нулей и единиц, только умножение заменяется на AND, а сложение на XOR.

← →
jack128 © (2005-01-18 23:40) [4]

palva © (18.01.05 23:38) [3]
а сложение на XOR
почему на xor то?? Может на or?

← →
MBo © (2005-01-18 23:47) [5]

>palva © (18.01.05 23:38) [3]
Вот и хотелось бы от автора точно узнать, как именно должно быть.
Про бинарное представление + транспонированная матрица - все разумно. Я полагаю, что может быть не xor, а or.

← →
palva © (2005-01-18 23:48) [6]

jack128 © (18.01.05 23:40) [4]
Сложение по модулю два, т. е. 1+1=0. Так должно быть. Получается XOR.

Ведь у сложения должно быть и вычитание. Если бы было
1+1=1, то отнимем от обеих частей единицу, получим 1=0, что нехорошо.

← →
palva © (2005-01-18 23:54) [7]

Если я неправильно понял и нужен OR, тогда нужно проверять не флаг четности а флаг нуля

← →
d-alone (2005-01-19 18:18) [8]

Поясню
1*1=1
1*0=0*1=0*0=0
1+1=1+0=0+1=1
0+0=0
дальше матрицы из нулей и единиц перемножаются как обычные строка-на-столбец, только с соответствующими операциями.
каждую матрицу я кодирую соответствующим десятичным числом напрмер для размерности 3*3
1 0 0
0 1 0
1 1 0

выписываю построчно : 100010110
и перевожу в десятичный вид: 278

Задача: сложность обыкновенного умножения О(n^3)
необходимо умножение делать быстрее т.е. если работать с десятичными представлениями, то получается О(n^2) у меня огромная прога - и это самое узкое место
Большое спасибо будет тому, кто сообразит как развить алгоритм вынесенный в тему или тому кто предложит как бысто умножить эти матрицы

← →
default © (2005-01-19 18:28) [9]

d-alone (19.01.05 18:18) [8]
1+1=1
если в суммировании появляется хоть одна единица то можно считать результатом 1 без разницы есть ли ещё единичные слагаемые
то есть тут будет прибавка в скорости
она будет и в сложении и в умножении(поскольку при умножении тоже сложение есть)

← →
Jeer © (2005-01-19 18:32) [10]

Так может и надо заниматься логическими операциями, а не арифметическими ? (palva © (18.01.05 23:38) [3])
Если размерность - константа и форму хранения матриц можно выбирать, то можно упростить.

← →
default © (2005-01-19 18:34) [11]

Jeer © (19.01.05 18:32) [10]
ясен перец
дело в том что он не знает как это закодировать
я бы написал соотв-ий класс

← →
palva © (2005-01-19 18:57) [12]

Побайтно надо кодировать. Каждую строчку в отдельном байте. Тогда не будет сдвигов перед умножением. Только размерность при этом будет ограничена числом 8. Я сначала понял, что размерность фиксированная - 6. Перед умножением хорошо было бы правый сомножитель транспонировать, то есть перейти к хранению по столбцам. Чем больше размер матрицы, тем большую выгоду это даст. Вычисление одного элемента результирующей матрицы сведется тогда к команде AND между байтами и проверке флага. Если 1+1=1, то нужно проверять флаг нуля, то есть на этом этапе можно обойтись без ассемблера. Хуже, когда придется записывать результат в произведение. Если он должен быть в том же закодированном виде, что и сомножители, надо будет уметь установить определенный бит. Ассеблер позволяет сделать это очень эффективно, без сдвигов.

1+1=1 это называется не логическое сложение а дизъюнкция. Или иначе 1V1=1. Конечно, хозяин - барин. Но тогда перемножение матриц будет очень странным. При таком определении сложения летит к чертям вся теория определителей и обратных матриц, то есть невырожденные матрицы уже не будут являться группой по умножению.

← →
d-alone (2005-01-19 19:31) [13]

Булевы матрицы относительно данных операций образуют циклическую полугруппу. Можно не привязываться к кодированию матриц. Мне необходимо как-то ускорить работу алгоритма умножения матриц. Жду предложний. А логическое сложение и дизъюнкция - это одно и тоже- не путайте со сложением по модулю 2 - там 1+1=0.
Буду очень благодарен если кто-то накидает процедуру умножения двух матриц размерности от 3*3 до 7*7

← →
default © (2005-01-19 19:47) [14]

d-alone (19.01.05 19:31) [13]
так размер матрицы только 6*6 или... как?

← →
Jeer © (2005-01-19 20:46) [15]

default © (19.01.05 19:47) [14]

Это называется - "Новые вводные" :))))
Зачем мне чай, если есть кофе или на худой конец коньяк:)

← →
d-alone (2005-01-19 22:30) [16]

ограничиваемся 6*6 (если что я там сам допридумываю), просто на мой взгяд процесс умножение для матриц размерности от 2*2 до 8*8 будет одинаков, вот когда за байт вылезет, тогда возникают другие сложности, кстати всего матриц размерности 6*6 - 2^36 - т.е. это уже больше 32 бит. в своей проге я использую int64.
Ну так кто- небудь даст дельный совет?

> А логическое сложение и дизъюнкция - это одно и тоже
Ну, я ведь и не спорю.

> Мне необходимо как-то ускорить работу алгоритма умножения матриц.

Ускорить по сравнению с чем? В каком виде вы получаете матрицу на входе? Каждая матрица участвует только в одном умножении? Если да, то ничего ускорить нельзя. Усилия на подготовку двух матриц сожрут любое ускорение при умножении матриц такого маленького порядка

> Кол-во сдвигов уменьшается с N^3 до N^2

Все эти рассуждения существенны, когда N достаточно велико, когда основное время расходуется собственно на умножение матриц. Тогда действительно стоит добиваться ускорения умножения. да и не получается O(N^2), потому что при больших N строка матрицы не уложится в одно машинное слово, вам придется организовывать внутренний цикл по этим словам и у вас добавится множитель, пропорциональный N.

> Идея следующая: каждую матрицу закодировать десятичным числом

Идея плохая. Зачем кодировать десятичным, если для работы ее нужно опять переводить в двоичное. Зачем кодировать одним числом, объединяя несколько чисел соответствующих строкам, если при работе алгорима придется всё равно разбивать это число на первоначальные составляющие? Было бы лучше кодировать, как я уже два раза предлагал, но боюсь что это тоже бесполезно. Ускорения на таких маленьких матрицах вы не получите, поскольку много времени уйдет на перекодирования.

Имхо.

d-alone (19.01.05 22:30) [16]
все советы по алгоритму уже розданы осталось уже только писать
лично я пока не вижу явной нужды тут применять ассемблер
(если Вы поняли о чём говорилось в [12] и ранее)
советую всё реализовать классом
будет операция, например, MatrObj.Add(A, "Name")
то есть операция кодирования матрицы A и присвоение ей определённого имени для использования потом в вычислениях
(либо обращаться к ней по индексу - как лучше Вам решать естественно Вам)
на счёт удобства произведения операций
нужно допустим вычислить выражение A*B+C*D+E
или Вы будете писать что-то типа
MatrObj.Sum(MatrObj.Sum(MatrObj.Mult(1, 2), MatrObj.Mult(3, 4)), 5)
цифры - это индексы закодированных матриц либо как говорил используйте имена
или же как-то по-другому
например, MatrObj.Calc([1, 2, 3, 4, 5], "*+*+")
с соблюдение приоритета операций если нужно
вообщем сами решайте как Вам лучше сделать

← →
d-alone (2005-01-19 23:42) [19]

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

если ответ на следующий вопрос положительный
Каждая матрица участвует только в одной операции?
то перекодировка мало чего даст если вообще не заберёт(особенно на маленьких матрицах)
об этом говорилось в [17]
я подразумевал что ответ на вопрос выше отрицательных раз Вы взялись за кодирование матриц...

d-alone (19.01.05 23:42) [19]
вообщем правильно делать как написано в [12]
оптимальней с точки зрения идеи я думаю некуда

← →
d-alone (2005-01-20 22:20) [22]

Спасибо за советы, попробую это реализовать. Кодировка работает быстро, самое главное написать быстрое умножение двух матриц, которое работало бы быстрее стандартного перемножения двух массивов, а кодировка нужна лишь для того, чтобы их можно было быстрее сравнивать, не делая проходов по строкам и столбцам массива, но кодировка в принципе зависит от процедуры умножения и особой роли не играет поскольку работает относительно быстро.

Быстрое умножение булевых матриц Найти похожие ветки