библиотека для полных SVD разреженных матриц
Я хочу сделать разложение по сингулярным числам для больших матриц, содержащих много нулей. В частности, мне нужны U и S, полученные из диагонализации симметричной матрицы A. Это означает, что A = U * S * транспонировать (U ^ *), где S — диагональная матрица, а U содержит все собственные векторы в виде столбцов.
Я искал в Интернете библиотеки c ++, которые объединяют SVD и разреженные матрицы, но я мог найти только библиотеки, которые находят несколько, но не все собственные векторы. Кто-нибудь знает, есть ли такая библиотека?
Также после получения U и S мне нужно умножить их на некоторый плотный вектор.
Решение
Для этой проблемы я использую комбинацию различных методов:
-
Arpack может вычислить набор собственных значений и связанных собственных векторов, к сожалению, он быстр только для высоких частот и медленный для низких частот
-
но так как собственные векторы обратной матрицы совпадают с собственными векторами матрицы, можно разложить матрицу (используя подпрограмму факторизации разреженной матрицы, такую как SuperLU или Choldmod, если матрица симметрична). «Протокол связи» с Arpack ожидает только того, что вы вычислите матрично-векторное произведение, так что если вы решаете линейную систему, используя вместо этого факторизованную матрицу, то это делает Arpack быстрым для низких частот спектра (не забывайте тогда заменить собственное значение лямбда на 1 / лямбда!)
-
Этот прием можно использовать для изучения всего спектра с помощью обобщенного преобразования (преобразование в предыдущей точке называется преобразованием «инвертирование»). Существует также преобразование «сдвиг-инверсия», которое позволяет исследовать произвольную часть спектра и иметь быструю сходимость Arpack. Затем вы вычисляете (1 / лямбда + сигма) вместо лямбды, когда сигма — это «сдвиг» (преобразование немного сложнее, чем «обратное», см. Ссылки ниже для полного объяснения).
ARPACK: http://www.caam.rice.edu/software/ARPACK/
SUPERLU: http://crd-legacy.lbl.gov/~xiaoye/SuperLU/
Численный алгоритм объясняется в моей статье, которую можно скачать здесь:
http://alice.loria.fr/index.php/publications.html?redirect=0&Бумага = ManifoldHarmonics @ 2008
Исходный код доступен там:
https://gforge.inria.fr/frs/download.php/file/27277/manifold_harmonics-a4-src.tar.gz
Смотрите также мой ответ на этот вопрос:
https://scicomp.stackexchange.com/questions/20243/sparse-generalized-eigensolver-using-opencl/20255#20255
Другие решения
Других решений пока нет …