Текст написан в декабре 2007 года для группы http://groups.google.com/group/matrixprogramming_ru
См. также http://matrixprogramming.rudnyi.ru/
Я хотел бы поделиться своими соображениями по поводу библиотек на С++ по линейной алгебре. Если поискать в Usenet, то можно увидеть, что регулярно на протяжении последних лет пятнадцати задается вопрос, а какую библиотеку по линейной алгебре на С++ следует использовать. Соответственно, было много разработок на эту тему. Однако и сейчас дать однозначный ответ на этот вопрос, по-моему, нельзя.
Я по ходу пробовал использовать несколько библиотек, но затем по ряду причинам, все завершилось тем, что я просто сам вызывал разных решателей из моего кода на С++. Я не хочу сказать, что это наилучшее решение, но вот так вышло.
Основная причина, наверное, была недостаток времени. Мне нужно было быстро решить мою задачу, в которой основная нагрузка была связана с решением системы линейных уравнений, а функциональность, связанная с матричными операциями требовалась достаточно ограниченная, и оказалось, что было проще реализовать ее самому.
Однако могу назвать и другие причины. Функциональность библиотек была ограничена, в особенности лет десять назад. Получалось так, что вот как раз того что требовалось, там и не было. Последняя попытка у меня было несколько лет назад, когда я хотел взять GMM++. Изучил документацию, начал тесты прогонять, и тут то и выяснилось, что в ней нет представления для симметричных матриц (когда хранится только половина матрицы). А для меня это было критично, поскольку я работал с разреженными матрицами большой размерности.
С другой стороны, для быстрой разработки (prototyping) появились среды типа Matlab, Matematica и другие, где уже как раз вся линейная алгебра была представлена. Я сам работал с Matematica и могу сказать, что проверить идею в ней гораздо быстрее, чем программировать на С++. Здесь также могу привлечь внимание к SciPy и NumPy. Я сейчас переключился на их использование. NumPy, как мне кажется, дает очень неплохой интерфейс к LAPACK.
В этой связи появляется вопрос, а насколько сейчас нужна библиотека по линейной алгебре на С++. Использование интерпретатора типа Python, который дает интерфейс к откомпилированным и оптимизированным решателям мне представляется вполне перспективным. На этом пути можно сочетать средства быстрой разработки с неплохой производительностью. Собственно говоря, и Matlab, и Matematica делают тоже самое.
Было бы также интересно написать историю библиотек по линейной алгебре на С++, как развивались идеи. Это, наверное, дало бы много пищи для размышлений.
29.05.2010 Книга The Science of Programming Matrix Computations
Текст написан в марте 2008 года для группы http://groups.google.com/group/matrixprogramming_ru
Совсем недавно вышла крайне интересная книга — The Science of Programming Matrix Computations. Книга описывает метод программирования, используемый в FLAME (Formal Linear Algebra Method Environment). Пара комментариев идет ниже.
Первое, что приходит в голову при знакомстве с книгой, это «Безумству храбрых поем мы песню». BLAS и оптимизированный BLAS уже являются стандартом в использовании численных методов и разработка альтернативы тому, что уже широко используется на практике, является достаточно неблагодарным делом. Практики, как я например, просто используют то, что доступно в наличии. У разработчиков, как правило, просто нет времени в принципе. В общем, поезд мчится полным ходом и убедить находящихся там людей, что вот, можно это и лучше сделать, крайне непростая задача.
Пример из NA Digest. Там проф. Robert van de Geijn (автор книги) высказал свои соображения и получил в ответ от разработчика NASTRAN Louis Komzsik:
‘I believe that the lively FORTRAN vs. MATLAB discussion exposed another disconnect between the academia and the industry. I assumed that the ultimate goal of this discussion was the education of industrially employable professionals and not a future generation of educators! With all due respect to the importance of abstraction and the convenience of APIs, the comment of «the indices rearing their ugly heads» by an esteemed professor from a very highly regarded institution has just demonstrated aforementioned disconnect.’
Однако более детальное прочтение книги оставляет благоприятное впечатление. В книге описывается новый метод построения алгоритмов, при котором использовании верификации является органической частью разработки. Я помню, когда-то давно я читал Вирта «Алгоритмы+структуры данных=программы » и там в первый раз столкнулся с идеей верификации программ. Сама идея мне крайне понравилось, но как находить инвариант цикла, я так и не понял. На этом практическое использование идеи верификации в моей работе и закончилось. Книга The Science of Programming Matrix Computations показывает шаг за шагом, как идею верификации можно использовать для алгоритмов, связанных с матрицами.
Очень интересной является глава 5 «High Performance Algorithms». Вопрос достижения максимальной производительности уже затрагивался в нашей группе. Глава 5 книги дает хороший ответ на этот вопрос.
В заключение хочу отметить, что как естественное продолжение книги можно рассматривать следующую диссертацию
Paolo Bientinesi, Mechanical Derivation and Systematic Analysis of Correct Linear Algebra Algorithms. Ph.d. Dissertation, Department of Computer Sciences, University of Texas at Austin, August 2006.