2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбиение матрицы (массива)
Сообщение19.03.2012, 21:40 
Не подскажите существует ли оптимальный алгоритм разбиения произвольной матрицы $N \times N$ на равные сегменты. Примерно вот так:

$\begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14}  \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44}  \end{pmatrix}
\to
$\begin{pmatrix} a_{11} & a_{12}  \\ a_{21} & a_{22}   \end{pmatrix} +
$\begin{pmatrix} a_{13} & a_{14}  \\ a_{23} & a_{24}   \end{pmatrix} +
$\begin{pmatrix} a_{31} & a_{32}  \\ a_{41} & a_{42}   \end{pmatrix} +
$\begin{pmatrix} a_{33} & a_{34}  \\ a_{43} & a_{44}   \end{pmatrix}
$

Здесь показан один итерационный шаг, поскольку матрица небольшая. Дальнейшее разложение бессмысленно, поскольку дальше идут отдельные элементы матрицы. Задача достаточно проста, если $N$ кратно степени 2-ки. Результатом алгоритма будет серия $\frac{N}{2}\times \frac{N}{2} \to \frac{N}{4} \times \frac{N}{4} \to \frac{N}{8} \times \frac{N}{8} \to ... \frac{N}{2^k} \times \frac{N}{2^k}$, здесь $\frac{N}{2^k}=2$ (размер элементарной ячейки=матрицы минимального размера). А если нет? Хотелось бы узнать, существует ли доказанный оптимальный алгоритм такого разбиения. И как быть в случае нечётного $N$. Скорее всего необходимо выбирать размер элементарной ячейки соответствующий и наверно будут существовать матрицы, которые не могут быть оптимально разбиты на равные части. Тогда второй вопрос: существует ли алгоритм разбивающий матрицу с минимальными потерями начальных ограничений?

 
 
 
 Re: Разбиение матрицы (массива)
Сообщение19.03.2012, 21:50 
Вы не указали ни критерия оптимальности, ни "начальных ограничений", поэтому пока вопрос бессмысленен.

 
 
 
 Re: Разбиение матрицы (массива)
Сообщение19.03.2012, 21:55 
venco в сообщении #550127 писал(а):
Вы не указали ни критерия оптимальности, ни "начальных ограничений", поэтому пока вопрос бессмысленен.

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

 
 
 
 Re: Разбиение матрицы (массива)
Сообщение19.03.2012, 22:22 
Но можно на одном шаге разбить, скажем, на 4 матрицы (каждую сторону пополам), а на следующем - на 9 (сторону на 3 части)? Тогда - всего лишь найти все простые множители для числа N.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group