Увеличение лидирующих нулей в симметричной разреженной матрице

В предыдущей статье было показано, что при решении СЛАУ с симметричной разреженной матрицей наличие лидирующих нулей приводит к уменьшению количества вычислений. В этой статье будет представлен алгоритм, предназначенный для увеличения количества лидирующих нулей данной матрицы. Если переставить i-ую и j-ую строки, а также i-ый и j-ый столбцы, то матрица останется симметричной. Такие перестановки называют симметричными. Они могут менять количество лидирующих нулей и, если их правильно применять, то количество лидирующих нулей можно увеличить. Другими словами, нам надо сделать так, чтобы все ненулевые члены по возможности находились возле главной диагонали. В частности, если известно, что матрица - ленточная, то делать ничего не надо. Предлагается следующий алгоритм. Вначале выбираем столбец ( или строку, что неважно, так как матрица симметричная ) с минимальным числом ненулевых элементов. Если таких столбцов несколько, то выбирается какой-то из них. При помощи симметричной перестановки делаем этот столбец первым. Таким образом количество нулей в этом столбце будет максимальным. Далее строки в которых были не нули игнорируем. Находим столбец с минимальным числом ненулевых элементов без учёта этих строк и делаем его следующим. И так далее пока не пройдём всю матрицу. Ниже помимо краткого текстового описания программы приводится много кода на С++, который сам по себе является точным описанием алгоритма.

https://habr.com/ru/articles/859170/

#слау #линейная_алгебра

Ускорение LUP-разложения матрицы с помощью OpenCL

Я являюсь автором проекта по математическому моделированию прикладной механики и в работе моей программы до 90% вычислительного времени уходит на решение системы линейных уравнений. Цель этой статьи сугубо практическая - найти оптимальный метод решения системы линейных уравнений с точки зрения производительность/трудозатрат для небольшого проекта и рассказать о результате. В прошлом я уже несколько раз обращал внимание на вычисления на GPU, но всегда что-то останавливало. И вот у меня накопился достаточный практический опыт программирования на C/C++ и наконец дошли руки, чтобы протестировать OpenCL.

https://habr.com/ru/articles/857568/

#линейная_алгебра #opencl #вычисления #с++ #gpu_вычисления

Решение СЛАУ с симметричной разреженной матрицей

В этой статье мы будем рассматривать решения СЛАУ вида Ax = b, где A - симметричная разреженная матрица. Такие матрицы появляются, например, при решении задач методом наименьших квадратов. Для симметричных СЛАУ разработаны специальные методы, такие, как метод Холецкого и LDL T разложение. Так как первый из них применим к более узкому классу матриц, чем второй, поэтому далее будем рассматривать только LDL T разложение, хотя выводы этой статьи применимы к обоим методам.

https://habr.com/ru/articles/854256/

#СЛАУ #линейная_алгебра

В поиске собственных значений (матриц)

Как найти собственные числа и собственные значения матрицы? Методы, излагаемые в курсе линейной алгебры, основанные на определении — применимы ли они к реальным данным? Существует ли простой алгоритм поиска этих величин, который можно понять, а не просто поверить? Об этом мы поговорим под катом

https://habr.com/ru/companies/ruvds/articles/845652/

#math #математика #линейная_алгебра #численные_методы #ruvds_статьи

Вычисления на RISC-V: исследуем производительность OpenCL на CPU и совместимых GPU

библиотек в YADRO. Эта сфера активно развивается на RISC-V: известные математические библиотеки, такие как OpenBLAS, Eigen и многие другие, портируются и оптимизируются под RISC-V. Большой интерес представляет OpenCL — открытый стандарт разработки программного обеспечения для гетерогенных вычислений. Он широко используется во многих областях: HPC, AI/ML, AR/VR, линейная алгебра. В линейной алгебре OpenCL наиболее широко представлен с помощью библиотек clBLAS и CLBlast. Первая — более старая, вторая — более современная, со встроенным тюнером для оптимизации под конкретное железо. Далее я расскажу о своем проекте с летней стажировки: исследовании производительности этих библиотек на GPU

https://habr.com/ru/companies/yadro/articles/847960/

#riscv #opencl #математические_библиотеки #линейная_алгебра

Знакомимся с линейной алгеброй в NumPy

Краткий гид по основам библиотеки NumPy и основным линейно-алгебраическим операциям с её использованием Читать!

https://habr.com/ru/articles/841578/

#линейная_алгебра #векторы #матрицы #numpy #python

Баланс стоимости предметов в RPG с помощью линейной алгебры

Я обожаю RPG, меня привлекают их богатый сюжет, стратегическая глубина и захватывающие миры. Также меня восхищают data-driven подходы к разработке. Они не только улучшают логическую структуру игровых механик, но и гарантируют, что каждый элемент игры сбалансирован и вносит значимый вклад в опыт игрока. Баланс - один из самых сложных аспектов разработки игр, поскольку он требует тщательного внимания к взаимодействию игровых механик. Сегодня я расскажу о том, как использовать линейную алгебру для баланса стоимости предметов в игре.

https://habr.com/ru/articles/836776/

#баланс #линейная_алгебра

Погружение в матрицу: расширение RISC-V от T-Head

Продолжим нашу «антологию матричных расширений» текстом про независимое матричное расширение RISC-V от компании T-Head. Почему мы рассматриваем именно его? Интересно понять, что из себя представляет будущее стандартное матричное расширение RISC-V, попробовать реализовать алгоритм с его использованием, соотнести это со своим предыдущим опытом низкоуровневых оптимизаций. Кроме того, это интересная возможность попробовать написать программу для расширения, которого еще нет ни в одном процессоре, и запустить ее на эмуляторе. А еще ISA этого расширения весьма минималистична и, на мой взгляд, идеально подходит для тех, кто никогда не использовал матричные расширения в своем коде, но хочет попробовать (или узнать, как это выглядит изнутри). Не переживайте, текст не требует опыта низкоуровневых оптимизаций математических библиотек: погружение в матрицу будет постепенным. Начать погружение

https://habr.com/ru/companies/yadro/articles/827434/

#thead #матричное_расширение #матричное_умножение #операции #risvv #низкоуровневая_оптимизация #библиотеки #линейная_алгебра

No fail, no gain: как мы исправили более миллиона тестов, проверяя оптимизацию библиотеки OpenBLAS под RISC-V

Открытая архитектура RISC-V активно развивается: в стандарт добавляются новые расширения и инструкции, разрабатываются новые ядра и SoC. Поскольку многие компании видят перспективы архитектуры и готовы использовать ее в продакшене, создается программный стек для высокопроизводительных вычислений — RISC-V HPC (High Performance Computing). Прогресс сопровождает формирование нового тренда — OpenHPC. Он заключается в технологической независимости от решений коммерческих компаний. Причем это относится не только к ПО, но и к железу. Чтобы концепция OpenHPC реализовывалась быстрее, нужно, чтобы к инициативе присоединилось как можно больше компаний, помогающих в развитии экосистемы решений для RISC-V HPC. Меня зовут Андрей Соколов, я инженер-программист в компании YADRO. В R&D-команде мы поставили перед собой задачу: изучить, как можно поддержать архитектуру RISC-V со стороны библиотек линейной алгебры BLAS и LAPACK. Тестирование одной из open source-библиотек привело нас к интересным открытиям, о которых я расскажу под катом. Результаты тестов

https://habr.com/ru/companies/yadro/articles/821715/

#openblas #blas #lapack #линейная_алгебра #библиотеки #оптимизация #riscv

Решение систем линейных уравнений с помощью Python

Как-то я наткнулась на статью , где говорилось о SymPy , а именно о возможности решения систем уравнений с ее помощью. Если кратко, то это бесплатная библиотека для символьных вычислений на языке Python. В символьных вычислениях компьютер работает с уравнениями и выражениями как с последовательностью символов, тогда как в численных оперирует приближёнными числовыми значениями. И поскольку линейные уравнения встречаются не только в математике, а также и в физике, и в ифнформатике, и во многих других областях, мне бы хотелось рассмотреть возможность их решения с Python. Приятного прочтения)

https://habr.com/ru/companies/bothub/articles/807413/

#математика #алгебра #линейная_алгебра #система_уравнений