логические операции над матрицами

[rootkid]

Всем привет, подскажите, пожалуйста, есть ли такая вещь как subj? eg:

0 1 0
1 0 0
0 1 0
&
0 1 0
1 1 0
1 0 0
=
0 1 0
1 0 0
0 0 0

т.е.

A&B=C

интересует более-менее академический подход и алгоритмы луче полного перебора, спасибо.

Comments

[alex_djk1]

А что вы пытаетесь найти? Можно ли так делать? Оптимальные способы? Еще что-то?

[rootkid]

пытаюсь найти результирующую матрицу, каждый элемент которой получается в результате логической операции между двумя данными

[alex_djk1]

Не хочу казаться капитаном очевидность, но может просто к одинаковым элементам (в плане позиции) применить операцию?

[rootkid]

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

[alex_djk1]

Обьедините элементы строк в байты и делайте побайтовые операции, а не побитовые.

[antilamer]

Матрицы разреженные или имеют особую форму? Если нет (произвольные) то очевидно ничего сделать нельзя - невозможно вычислить результат, не ознакомившись со входными данными, т.е. вопрос лишь в том, насколько компактно можно представить интересующие вас матрицы.

[rootkid]

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

"возможно, но если отвлечься от конкретного примера, в какую сторону можно копать A&B=C ?"

[diam_2003]

Если это матрицы специального вида, про которые вам довольно много известно, вы явно что-то недоговариваете. Алгоритмов умножения матриц специального вида есть сколько-то, все разные :)

[gegmopo4]

Какая же это пермутация? У вас несколько единичек в строке или столбце.

[rootkid]

>>такой пример выбран лишь для наглядности,

[gegmopo4]

Какая же тут наглядность, если уводит в неверном направлении? Предоставьте правдивое условие, если хотите получить ответ на свой вопрос.

[antilamer]

Мне кажется, Вы то ли не понимаете чего-то фундаментального, то ли неправильно формулируете вопрос

[rootkid]

да, хотелось бы выполнить операцию над данными размера N за менее чем N операций в надежде на то, что структура данных известна (http://ru-algorithms.livejournal.com/102901.html?thread=1082357#t1082357)

допустим элемент равен 1 если сумма его индексов(i,j), разделенная на кол-во строк(m)-простое число, иначе 0, две матрицы m*n и (m-1)*n, вторую (более короткую) сверху дополнить нулями до m.

[antilamer]

Вас интересует конкретно эта закономерность, или Вы хотите программу, которая сама догадается, что там за закономерность? Второе теоретически невозможно. Для каждой конкретной закономерности нужно думать отдельно.
См.тж. operations on compressed data - некоторые способы сжатия позволяют делать некоторые операции над сжатыми данными, не разжимая их. Но для этого нужно, чтобы данные хорошо поддавались сжатию данным конкретным способом. Квадродеревья, кстати, один из таких способов для разреженных матриц.

[rootkid]

спасибо