Что такое разреженная матрица
Перейти к содержимому

Что такое разреженная матрица

  • автор:

Разреженные матрицы

Разреженные матрицы обеспечивают эффективное устройство хранения данных double или данных logical , которые имеют большой процент нулей. В то время как полный (или плотный ) матрицы хранят каждый элемент в памяти независимо от значения, разреженные матрицы хранят только ненулевые элементы и их индексы строки. Поэтому использование разреженных матриц может значительно уменьшать объем памяти, требуемый для хранения данных.

Весь MATLAB ® встроенная арифметика, логическая, и операции индексации, может быть применен к разреженным матрицам, или к смесям разреженных и полных матриц. Операции на разреженных матрицах возвращают разреженные матрицы, и операции на полных матрицах возвращают полные матрицы. Для получения дополнительной информации смотрите Вычислительные Преимущества Разреженных матриц Построения и Разреженных матриц.

Функции

Создание

spalloc Выделите место для разреженной матрицы
spdiags Извлеките и создайте разреженную полосу и диагональные матрицы
speye Разреженная единичная матрица
sprand Разреженная равномерно распределенная случайная матрица
sprandn Разреженная нормально распределенная случайная матрица
sprandsym Разреженная симметричная случайная матрица
sparse Создайте разреженную матрицу
spconvert Импортируйте из внешнего формата разреженной матрицы

Манипуляция

issparse Определите, разреженно ли введенный
nnz Количество ненулевых элементов матрицы
nonzeros Ненулевые элементы матрицы
nzmax Сумма устройства хранения данных выделяется для ненулевых элементов матрицы
spfun Примените функцию к ненулевым элементам разреженной матрицы
spones Замените ненулевые элементы разреженной матрицы на единицы
spparms Установите параметры для стандартных программ разреженной матрицы
spy Визуализируйте шаблон разреженности
find Найдите индексы и значения ненулевых элементов
full Преобразуйте разреженную матрицу в полное устройство хранения данных

Переупорядочение алгоритмов

dissect Вложенная перестановка рассечения
amd Аппроксимируйте минимальную перестановку степени
colamd Столбец аппроксимированная минимальная перестановка степени
colperm Разреженная перестановка столбца на основе ненулевого количества
dmperm Разложение Дулмаге-Мендельсона
randperm Случайная перестановка
symamd Симметричная аппроксимированная минимальная перестановка степени
symrcm Разреженное упорядоченное расположение обратного алгоритма Катхилла-Макки

Итеративные методы и предварительные формирователи

pcg Предобусловленный метод сопряженных градиентов
minres Метод минимальных невязок
symmlq Симметричный метод LQ
gmres Обобщенный метод минимальных невязок (с перезапусками)
bicg Бисопряженный метод градиентов
bicgstab Бисопряженные градиенты стабилизировали метод
bicgstabl Бисопряженные градиенты стабилизированный (l) метод
cgs Методы сопряженных градиентов придали методу квадратную форму
qmr Метод квази-минимальных невязок
tfqmr Метод квази-минимальных невязок без транспонирования
lsqr Метод LSQR
equilibrate Матрица, масштабирующаяся для улучшенного создания условий
ichol Неполная факторизация Холесского
ilu Неполная LU-факторизация

Объясните, что такое разреженные матрицы, как их генерировать и математические операции над ними

Скажите, пожалуйста, правильно ли я думаю.
На сколько я понял разреженная матрица — это матрица вроде этой:

1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 

Если это разреженная матрица — то генерировать ее элементы можно функцией rand() : rand()%2 Идентичен ли этот вид матриц квадратным матрицам (ряды=столбцам)? Математические операции (+,-,*,/) проводятся так же?
Спасибо!

Отслеживать
33.1k 2 2 золотых знака 33 33 серебряных знака 67 67 бронзовых знаков
задан 2 ноя 2018 в 14:38
Boris Makhlin Boris Makhlin
521 5 5 серебряных знаков 12 12 бронзовых знаков

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

2 ноя 2018 в 14:41
Какие шаги Вы предприняли, чтобы выяснить это самостоятельно?
– user176262
2 ноя 2018 в 15:12

@Igor Я читал в Википедии, но сугубо про математическую точку зрения. Более ничего не смог найти. Поэтому и обратился на этот форум

2 ноя 2018 в 15:43

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

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

Если же мы знаем, что ненулевых элементов в матрице будет в районе 0.1%, то есть порядка 1000, то представление матрицы и работу с ней можно сильно оптимизировать. Например, можно представить матрицу как простой массив ненулевых элементов, где каждый ненулевой элемент представлен такой структурой:

typedef struct < short row; short column; int value; >NonZeroElem; 

Тогда матрица вместо миллиона четырехбайтовых целых будет представлена всего лишь тысячью восьмибайтовых описателей. То есть 8кб вместо 4Мб — в пятьсот раз меньше.

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

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

Разреженные матрицы: как ученые ускорили машинное обучение на GPU

В начале декабря исследователи из OpenAI представили библиотеку инструментов, которая поможет ускорить обучение нейронных сетей на GPU от Nvidia за счет использования разреженных матриц. О том, с какими трудностями сталкиваются разработчики нейронных сетей и в чем основная идея решения от OpenAI, расскажем далее.

/ фото alantankenghoe CC

Трудности тренировки крупных нейронных сетей на GPU

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

Чтобы добиться схожего результата на центральном процессоре, придется выстроить инфраструктуру из нескольких кластеров CPU, что очень дорого. Система Google для тренировки нейросетей на CPU стоила порядка 5 млрд долларов. Сегодня ученые из Стэнфорда построили систему с аналогичной вычислительной мощностью на GPU всего за 33 тыс. долларов.

Однако здесь есть трудности: использовать весь потенциал GPU на ресурсоемких задачах не так просто. Для обработки данные должны храниться в памяти GPU, однако её объем невелик, что затрудняет тренировку крупных моделей. Например, модель VGG-16 требует около 14 ГБ, в то время как объем памяти Nvidia Titan X составляет 12 ГБ. И эту карту Nvidia позиционирует как один из самых мощных GPU для глубокого обучения.

Как верно заметил EvilGenius18 в комментариях, 7 декабря компания Nvidia представила новую карту Titan V на архитектуре Volta. Она обладает вычислительной мощностью 110 TFLOPS на задачах глубокого обучения, что в 9 раз больше, чем у предшественницы.

При этом для эффективной тренировки крупных моделей нейронных сетей используют различные подходы. Один из них — обработка данных на графическом процессоре последовательными партиями, когда CPU выступает временным контейнером. Минус такого подхода — расходование ресурсов на перенос данных.

Возможно одновременное использование нескольких графических процессоров, но количество GPU на одном компьютере ограничено, поэтому требуется высокоскоростное соединение между вычислительными системами. Межкомпьютерный канал связи сказывается на скорости обучения, поскольку машины в таком случае тратят больше времени на «общение», чем на вычисления.

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

Но есть проблема: решения Nvidia, главного поставщика GPU, не поддерживают работу с разреженными матрицами. Но в OpenAI нашли выход из этой ситуации.

Решение от OpenAI

Команда OpenAI разработала программное обеспечение, которое моделирует работу крошечных ядер, способных взаимодействовать с такими матрицами. Ядра опробовали на обучении сетей, анализирующих обзоры на сайтах Amazon и IMDB. Как сообщает команда, уровень ошибок в работе со сводом данных IMDB был снижен с 5,91% до 5,01%.

Ядра реализованы с использованием CUDA, программно-аппаратной архитектуры параллельных вычислений от Nvidia. Но модель OpenAI пока доступна только для TensorFlow. Скотт Грей (Scott Gray), член команды Open AI, сказал, что решение может быть распространено на другие архитектуры, кроме Google TPU2. Компания Nvidia уже знает о работе OpenAI и готова оптимизировать свои системы.

Альтернативные проекты

Концепция разреженных матриц получила свое воплощение в компиляторе с открытым исходным кодом под названием Taco. О проекте, над которым работает команда ученых из Массачусетского технологического института в партнерстве с Adobe Research, стало известно в ноябре. Разработчики искали способ автоматизировать процесс обработки чисел в разреженных матрицах. И использовали для этого тензоры.

О своих разработках в области машинного обучения в декабре отчиталась и компания IBM. Решение ИТ-гиганта — DuHL — предлагает новый метод переноса данных с CPU на GPU. Основная задача технологии — определить, какая информация наиболее важна для алгоритма обучения, и передать её сети в правильном порядке. Исследования показали, что новый подход на основе DuHL в 10 раз быстрее по сравнению с классическим методом последовательной передачи данных между процессорами. Следующая цель компании — предложить DuHL как услугу в облаке.

Но в IBM не первыми придумали переносить GPU-вычисления в облако. Подобные проекты, работающие в том числе по модели IaaS, уже известны. Изначально услугу vGPU предоставляла компания Nvidia. Сейчас этим занимаются и AMD, и Intel.

Об OpenAI

OpenAI — это некоммерческая исследовательская организация, основанная главой Tesla Илоном Маском. Она ставит своей задачей продвижение и развитие искусственного интеллекта на благо человечества. Организация плотно сотрудничает с другими учреждениями и исследователями, предоставляя открытый доступ к своим разработкам.

P.S. Еще несколько материалов из нашего корпоративного блога:

  • Как IaaS-облака помогают в проектах по сервисной разработке: кейс Azoft
  • BIM-технологии: обзор решени для информационного моделирования
  • Балансировка нагрузки в облаке IaaS: зачем нужна и как работает

Разреженная матрица

cover image

Разре́женная/разрежённая матрица — матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевая, матрица считается плотной или заполненной.

Эту страницу предлагается переименовать в « Разрежённая матрица ».

Эту страницу предлагается объединить со страницей Разреженный массив.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов [1] :

  • есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
  • в каждой строке не превышает 10 в типичном случае;
  • ограничено n 1 + γ > , где γ < 1 .
  • таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей [1] .

Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *