arrays — быстрое удаление столбцов из матриц. Переполнение стека

Question

arrays — быстрое удаление столбцов из матриц. Переполнение стека

Предположим, что у нас есть матрица A (m*n) хранится в упакованном виде (1-й массив размера m*n — с ведущими размерами — столбцы). Мне нужно получить уменьшенные матрицы A(S) — которые являются результатом удаления 1 или более столбцов из A, Я могу легко сделать это вручную в циклах, но есть другой подход — использование матриц выбора I(S) которые представляют собой единичные матрицы (все нули, кроме 1 по диагонали) с удаленным 1 или более столбцом. Тогда, например, если мне нужно удалить 3-й ряд из AМне нужно сформировать I(3) — личность без 3-го столбца, а затем A(3)=A*I(S), И так как мне нужно много вариантов AМне бы понадобились все разные тождественные матрицы I(S) с разными столбцами удалены.

Я думаю об этом, потому что я использую Intel Math Kernel Library — которая чрезвычайно эффективна для умножения матриц.

Так что вопрос в том, что вы думаете, самый быстрый способ формирования новой матрицы A(S): вручную, напрямую с A или первое формирование I(S) — и вопрос в том, как быстро сформировать эти матрицы — и затем умножить A*I(S) или вы можете предложить любое другое быстрое решение.

Для иллюстрации предположим, что у нас есть матрица A:

Хранится в массиве A=[1,4,7,2,5,8,3,6,9]. Suppose I need to formA (2) `то есть удалить 2-й столбец. Мне нужно иметь на выходе:

который хранится в C ++ как A_S=[1,4,7,3,6,9],
Это может быть сделано непосредственно на матрице А, которая будет принимать O(n^2) время и не эффективно для больших матриц. Или мы можем сформировать I(2):

хранится в C ++ как I_S = [1,0,0,0,1,0], затем A(2) = A*I(2)

1

arrays c++intel matrix multiplying

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я думаю, что вы должны быть осторожны, чтобы использовать I если ты имеешь ввиду identity matrix, Identity matrix как правило, квадратная матрица, в то время как вы используете обычно не квадратную матрицу, так как вы удалили столбец (столбцы) из исходной матрицы. Позвольте мне назвать матрицу преобразования как T, вместо I,

Сейчас я пытаюсь ответить на ваш вопрос:

вопрос в том, как быстро сформировать эти матрицы

так на основании вышеизложенного предположения, T(2) должно быть:

1  0
0  0
0  1

поскольку

1   2  3       1  0     1  3
4   5  6   *   0  0  =  4  6
7   8  9       0  1     7  9

Вы можете сравнить T(2) с оригинальным I(3) (здесь это единичная матрица) в зависимости от ситуации, когда вы удаляете второй столбец.

      1  0  0
I(3)  0  1  0
0  0  1

Поскольку вы знаете, какой столбец удалить, вы будете знать диапазон индексов одномерного массива, который вы использовали для хранения I(3)в данном случае это: A_I(3) = [1 0 0 0 1 0 0 0 1]; Вы знаете этот индекс [3,5] второй столбец, вам просто нужно удалить эти 3 значения, вы получите T(2) как в приведенном выше примере, который A_T(2) = [ 1 0 0 0 0 1], Таким образом, идея заключается в том, что если вы знаете, какой столбец исходной матрицы удалить, вы просто удалите значения из 1D-массива, в котором хранится единичная матрица в пределах диапазона индекса, в который отображается исходный столбец. В этом примере вы удаляете значения из [3,5] который 2nd столбец исходной матрицы отображается на.

Теперь вы можете использовать свою матричную библиотеку для умножения A а также A_T(2) и получить матрицу результатов.

1