|
В архиве новостей приведен список всех новостей библиотеки алгоритмов, всего 37 новостей. Последние новости находятся на странице новостей.
01.09.2010 Новый релиз - ALGLIB 3
Выпущена новая версия пакета ALGLIB - версия 3.0.0.rc1. В этой версии реализован ряд решений, существенно отличающих её от предыдущих релизов.
Во-первых, новая версия включает ряд обратно несовместимых изменений. Были изменены имена ряда функций, в некоторых случаях изменениям подвергся список параметров. Устаревшие конструкции, которые из-за соображений обратной совместимости переходили от версии к версии, были окончательно отброшены. Более подробно см. Change Log.
Во-вторых, по итогам обсуждения с пользователями библиотеки была проведена реструктуризация кода. Версия 2.6.0 включала в себя 104 модуля, и многим казалось не вполне удобным добавлять в свой проект 104 файла. В ALGLIB 3.x все модули были сгруппированы в 12 пакетов с простой структурой зависимостей, что облегчит жизнь всем пользователям библиотеки.
В третьих, изменилась концепция проекта. Раньше основной идеей проекта была автоматическая трансляция с псевдокода на каждый из используемых языков. Библиотека на FreePascal была полностью написана на FreePascal, библиотека на VBA была полностью написана на VBA. Этот подход очень привлекателен, но по мере того, как росли требования к библиотеке, становилось всё сложнее реализовывать одну и ту же функциональность в разных языках. Поэтому начиная с версии 3.0 концепция меняется - автоматический перевод делается только на те языки, которые позволяют легко реализовать всю требуемую от ALGLIB функциональность. Это C++, C#, C++ высокой точности. Для всех прочих языков будет автоматически генерироваться интерфейс к прекомпилированной версии на чистом C.
Столь масштабное изменение требует времени, поэтому сейчас мы можем представить вам только версию на C++. В самом скором времени будет реализована версия на C#, и вслед за ней - интерфейс для языка программирования Python. Ранее этот интерфейс уже анонсировался; планировалось представить его ещё в июне, однако в ходе разработки было решено представлять не промежуточную версию, а готовый к промышленному использованию продукт, полностью совместимый с новой веткой 3.x, в связи с чем релиз был перенесен на сентябрь.
На фоне крупных изменений становится менее заметной новая функциональность, однако в новой версии есть интересные добавления. Добавились алгоритмы решения нелинейных уравнений, функции для эффективного рестарта оптимизаторов, во многих подпрограммах появилась улучшенная обработка ошибок во входных данных. Неудобный интерфейс алгоритмов оптимизации, использующий обратную коммуникацию, наконец-то сменился более удобной версией, принимающей указатели на функции.
01.06.2010 Новый релиз - ALGLIB 2.6.0
В новой версии ALGLIB:
1. исправлено два бага (см. Change Log).
2. улучшены алгоритмы сплайн-интерполяции: добавлен сплайн Катмулла-Рома; добавлена поддержка периодических граничных условий.
3. реализованы алгоритмы параметрической сплайн-интерполяции в двух- и трехмерном пространстве. Параметрические сплайны поддерживают два типа граничных условий - непериодические и периодические.
Немного о планах на будущее. Новая версия ALGLIB мало изменилась по сравнению с ALGLIB 2.5.0 - если не считать улучшений сплайн-интерполяции, не было добавлено никаких новых алгоритмов. Причина тому - активная работа над очередным расширением пакета - работа над интерфейсом между ALGLIB и Python. Предполагается, что практически одновременно будет выпущен интерфейс к обычной, double precision версии ALGLIB, и к multiple precision версии, использующей MPFR. Ориентировочное время выхода новой версии пакета - июнь-июль 2010.
12.04.2010 Новый релиз - ALGLIB 2.5.0
В новой версии ALGLIB:
1. исправлено два бага (см. Change Log).
2. добавлены новые алгоритмы оптимизации: нелинейный метод сопряженных градиентов и алгоритм для оптимизации с простыми ограничениями на переменные.
3. переработан интерфейс двух уже имеющихся алгоритмов оптимизации: L-BFGS алгоритма и метода Левенберга-Марквардта. Изменены имена нескольких подпрограмм и структур данных, незначительно изменен набор параметров (часть параметров устанавливается по умолчанию, но может быть изменена при помощи вызова отдельной функции). Эти изменения являются обратно несовместимыми, однако модификация работающих программ не должна быть сложной.
10.03.2010 Новый релиз - ALGLIB 2.4.0
1. В новой версии ALGLIB улучшено быстродействие ряда алгоритмов линейной алгебры (главным образом, в C++ версии). Оптимизированы QR-разложение и обращение матриц, улучшен код алгоритма оценки числа обусловленности.
2. Добавлены новые алгоритмы: комплексные QR и LQ разложения, оценка числа обусловленности треугольных матриц, алгоритм поиска ближайших соседей на основе kd-деревьев и новый алгоритм многомерной интерполяции на нерегулярной сетке с трудоемкостью O(N·logN).
3. Мелкие исправления в одном из модулей (см. Change Log).
30.01.2010 Новый релиз - ALGLIB 2.3.0
1. В новой версии ALGLIB существенно увеличено быстродействие ряда алгоритмов линейной алгебры (главным образом, в версии ALGLIB на C++). Улучшена скорость работы BLAS первого уровня в C++ (за счет полного избавления от ООП). Реализован ряд cache oblivious алгоритмов BLAS второго и третьего уровня. Алгоритмы треугольной факторизации (LU-разложение и разложение Холецкого) переписаны в новом cache oblivious стиле. Алгоритм оценки числа обусловленности стал значительно более быстр, в том числе за счет избавления от излишних операций копирования матриц.
2. Добавлены новые алгоритмы: набор линейных солверов для систем с вещественными/комплексными/SPD/HPD матрицами.
3. Мелкие исправления (см. Change Log).
В планах на ближайшее будушее: повышение быстродействия и переписывание в cache oblivious стиле алгоритмов ортогональной факторизации (QR/QL/LQ/RQ, редукции к двух/трехдиагональным матрицам), дальнейшее повышение быстродействия C++ версии пакета за счет использования SSE.
18.01.2010 Новый релиз - ALGLIB 2.2.1
ALGLIB 2.2.1 содержит только исправления ошибок, а именно - неверного assertion в модуле minlm.
Декабрь, 2009. ALGLIB 2.2.0.
1. Одним из основных нововведений в ALGLIB 2.2.0 является система компиляции и тестирования. Теперь пакет может быть откомпилирован при помощи Bash-скрипта build (или одноименного пакетного файла - для пользователей Windows). Ещё один скрипт - check - служит для запуска тестов (для всего пакета в целом, или для модуля по выбору пользователя). К архиву с исходными кодами прилагается автоматически сгенерированный reference manual.
2. С использованием новой системы было проведено более широкое тестирование пакета на ряде систем и компиляторов и значительно улучшенная переносимость. По состоянию на момент выпуска ALGLIB протестирован на x86 и x86_64, в Windows и Linux, с компиляторами Microsoft, под GCC, Mono и FreePascal. В планах расширение списка поддерживаемых платформ (за счет добавления других архитектур и операционных систем) и компиляторов.
3. От Delphi-версии ALGLIB отделился новый язык программирования - FreePascal. Хотя с этим компилятором имеются мелкие проблемы, мне он более симпатичен, чем Delphi - в том числе благодаря своей бесплатности и кросс-платформенности.
4. Традиционно, новые исходные коды - список изменений можно посмотреть по адресу http://bugs.alglib.net/changelog_page.php
Октябрь, 2009. ALGLIB 2.1.2.
Релиз 2.1.2 - это очередной набор исправлений. В этой версии исправлены ошибка компиляции под GCC и ошибка в модуле reflections.
Сентябрь, 2009. ALGLIB 2.1.1.
Релиз 2.1.1 - это небольшой релиз, содержащий исправление ошибки в нейросетевом пакете. Более существенные изменения (обновленные алгоритмы интерполяции/аппроксимации) выйдут в версии 2.2.0, которая ожидается в ноябре 2009.
Сентябрь, 2009. ALGLIB 2.1.0.
Наиболее значимым изменением в версии 2.1.0 является смена лицензии. Решение о смене лицензии принималось нелегко. Около двух лет проект распространялся на основе лицензии BSD, однако по итогам этого периода стало ясно, что для дальнейшего развития проекта больше подходит GPL. В связи с этим, начиная с версии 2.1.0, ALGLIB распространяется на условиях GPL v2+ (версия 2 или более поздняя по выбору пользователя).
Смена лицензии, разумеется, затрагивает только версию 2.1.0 и последующие версии. Пользователи, использующие предыдущую версию (2.0.1), могут продолжать использовать пакет и распространять производный код на менее строгих условиях BSD. Это право гарантировано им лицензией. Однако старая версия больше не поддерживается - все исправления ошибок будут выпускаться на условиях GPL 2+ и только в составе новых версий. Не рассматривайте это, как попытку форсировать переход пользователей на GPL - это вынужденная мера. Поддержка пакета, распространяющегося сразу на пяти языках программирования, тяжела. Поддержка двух версий такого пакета - практически невозможна.
Кратко о других изменениях:
Изменения, приводящие к несовместимости с предыдущей версией:
Более детальная информация доступна в баг-трекере. Там же можно увидеть состояние работ над следующей версией пакета.
Июль, 2009. ALGLIB 2.0.1.
Версия 2.0.1 - это набор исправлений мелких и средних ошибок (см. баг-трекер). Из существенных изменений: повышено быстродействие алгоритма рациональной интерполяции; улучшена совместимость со средствами разработки, проверяющими наличие неинициализированных переменных.
Апрель, 2009. Обновления на сайте.
В течение длительного времени – почти год – сайт проекта не обновлялся. Столь длительный перерыв не обозначает, что проект прекратил развиваться – большую часть этого времени велась активная работа над новыми исходными кодами. И я рад сообщить пользователям ALGLIB следующие новости:
Встречайте – ALGLIB 2.0!
Многие пользователи ALGLIB сообщали о своем желании скачать все исходные коды в одном zip-архиве. Также многие пользователи сообщали, что отсутствие нумерации версий запутывает и не позволяет отслеживать изменения проекта. Действительно, в течение длительного времени проект развивался нетрадиционным путем – как набор модулей, из которых пользователь выбирал только необходимые ему. У такого подхода есть свои преимущества – например, он позволяет создавать компактные программы. Однако есть и недостатки – крайне сложно отслеживать все изменения в многочисленных модулях.
По этим причинам был изменен механизм доступа к исходным кодам. Теперь пользователи могут скачать весь проект в одном zip-архиве, хотя это не отменяет возможности помодульного скачивания ALGLIB. Индивидуальные модули по-прежнему не имеют номера версии, однако весь релиз в целом имеет номер, обновляющийся при каждом изменении. Текущей версии назначен номер 2.0.
Замечу, что нумерация версий начинается не с единицы, т.к. с 1999 года проект прошел немалый путь. Номер 2.0 отражает все изменения, произошедшие с ALGLIB за эти годы.
Немного о будущем…
Обозначу приоритетные задачи на ближайшее время:
Октябрь, 2008. Изменения на сайте:
linreg может использоваться для решения многомерных задач (ранее решались только одномерные задачи). Помимо собственно коэффициентов регрессии алгоритм возвращает погрешность найденных параметров и кросс-валидационную оценку ошибки регрессии, полученную быстрым алгоритмом. Добавлен ряд вспомогательных функций для работы с построенными линейными моделями: упаковка/распаковка и получение ошибки на тестовом множестве.
Июнь, 2008. Для начала сообщения об исправленных ошибках и добавленных алгоритмах:
А теперь наконец-то главная новость нескольких последних месяцев: выпущена ABLAS - библиотека базовых алгоритмов линейной алгебры, поддерживающая SSE2! Исходники на C++ уже могут использовать эту библиотеку, что приводит к значительному росту быстродействия. Другие языки пока не могут использовать её, однако в скором времени планируется добавить поддержку для C# и как-то решить вопрос с Delphi (есть некоторые сложности). ВНИМАНИЕ: для того, чтобы использовать ABLAS, вам необходимо скачать новую версию библиотеки AP:C++.
Апрель, 2008. Информация об изменениях на сайте.
К вопросу о сроках. Думаю, все уже поняли, что когда я говорю "январь", это значит в лучшем случае "март". На съевших большую часть времени направлениях борьбы получены следующие результаты:
Нейронные сети побеждены лишь частично. Мне удалось выложить в открытый доступ нечто завершенное, включающее в себя базовые алгоритмы обучения. Однако "продвинутые" темы - байесовская регуляризация и другие виды нейронных сетей, помимо обычного многослойного персептрона - эти темы пока остались нереализованными. Через некоторое неопределенное время (учимся не называть точных сроков) я выложу утилиту для работы с файлами данных (чтение обучающего множества из файла, простейшие виды конверсии).
Алгоритмы линейной алгебры разгромлены почти полностью (в лесу осталось несколько партизан, но кому они интересны?). Почти все доступные пользователю алгоритмы линейной алгебры принимают матрицы с современной нумерацией элементов (т.е. начинающейся с нуля). Почти все алгоритмы снабжены юнит-тестами. Результат выложен в открытый доступ. Для совместимости оставлены и старые версии алгоритмов, новые версии имеют другие имена. Несколько служебных алгоритмов не переведено в новый формат, однако это не должно мешать использованию библиотеки (эти алгоритмы не интересны широкой публике). Также с алгоритмами линейной алгебры связан ряд других улучшений, которые перечислены ниже.
Мой субпроект "ALGLIB:PROJECTS", состоящий в предложении интересным проектам бесплатного хостинга и своего раздела на посещаемом сайте, пока не принес никаких результатов. Я, признаться, ожидал большего - с учетом того, что не ищу от этого проекта какой-либо выгоды для себя лично. Что ж, похоже, не так уж и много людей имеет интересный проект, которым они хотят поделиться с окружающими. Но мое предложение остается в силе.
Прочие обновления:
Планы на будущее:
Ноябрь, 2007. Информация об изменениях на сайте.
С точки зрения пользователей, ноябрь был не очень плодотворным. На сайте появился лишь один новый модуль - высококачественный генератор случайных чисел (см. раздел "Статистика"). Впрочем, месяц не пропал зря - всё это время велась работа над нейронными сетями.
Многослойный персептрон уже доведен до ума, надо только придать ему приличный вид. С сетью каскад-корреляция были и есть некоторые сложности - я даже подозревал, что без применения черной магии эта сеть просто в принципе не будет работать - однако теперь она вроде бы заработала (так ли это, сейчас выясняется). Ожидаемый срок появления новых модулей - декабрь-январь. Хочу и надеюсь на декабрь, но там много надо сделать.
Смена системы нумерации в алгоритмах линейной алгебры ещё не завершена. Я делаю эту работу параллельно с другими проектами и не выложу результат, пока не переведу раздел полностью.
Теперь об обещанном ранее анонсе нового проекта. В связи с переездом моего сайта на более мощный сервер у меня появилось свободное место. Я хочу использовать его для предоставления хостинга интересным проектам из области вычислительной математики. Автор проекта получает собственный раздел, над содержимым которого он имеет полный контроль, и ссылки на этот раздел со страниц моего сайта. У моего сайта хорошая посещаемость, и я готов поделиться посетителями и позициями в поисковиках, размещая ваш проект у себя. Коммерческой подоплеки это предложение не несет. Более подробно о нем можно узнать на странице проектов. Если у вас интересный проект и вы хотите, чтобы о нем узнали - это для вас.
Октябрь, 2007. Информация об изменениях на сайте:
Теперь о том, что ещё находится в работе:
Ещё из отчетов о текущем состоянии - сайт переехал на новый, более производительный сервер. Судя по всему, переезд прошел незаметно для всех, что является показателем успешности операции.
Ну и в заключение: я сейчас готовлю анонс нового проекта... его можно назвать субпроектом Библиотеки Алгоритмов. Детали пока сообщать не буду, скажу только, что планирую анонсировать его в ноябре, и что он отчасти возродит традиции проекта manual.ru, который сейчас, скажем так, несколько неактивен.
31.03.07 За два последних месяца на сайте произошел ряд изменений, а именно (в порядке возрастания важности): добавление новых алгоритмов, добавление нового режима работы транслятора, начало работы над автоматизированным тестированием, изменение способа доступа к исходникам. Итак, по порядку.
Хотя я не планировал в ближайшие полгода заниматься добавлением на сайт новых исходников, т.к. сейчас гораздо важнее разобраться с тем, что уже есть, но в ходе работ по автоматическому тестированию алгоритмов было написано несколько полезных подпрограмм, которые могли бы пригодиться посетителям сайта: алгоритмы генерации случайных матриц с требуемыми свойствами (написаны алгоритмы для генерации случайных ортогональных матриц; случайных несимметричных, симметричных положительно определенных и знаконеопределенных матриц с требуемым числом обусловленности) и алгоритмы для поиска собственных чисел эрмитовых матриц (последнее получилось как-то само собой).
Был добавлен новый режим работы транслятора, который я давно хотел реализовать. Речь идет о трансляции алгоритмов в код на C++, использующий для вычислений арифметику высокой точности (используется open-source библиотека MPFR). Новый режим трансляции доступен только для тех алгоритмов, которые смогут воспользоваться его преимуществами - для алгоритмов линейной алгебры (очевидно, что, например, комбинаторные алгоритмы не нуждаются в вещественной арифметике - ни в обычной, ни в особо точной).
Начата работа над автоматическим тестированием алгоритмов. Собственно говоря, тестирование было и раньше, но, во-первых, не автоматизированное и не настолько обширное, как хотелось бы, и, во-вторых, посетителям сайта тесты не были доступны, что порой вызывало у них сомнения в надежности алгоритмов. Теперь же каждый может скачать вместе с алгоритмом тестирующий код и убедиться, что всё работает так, как и должно работать. Пока ещё не все алгоритмы снабжены автоматизированными тестами в новом формате, но в скором времени это будет исправлено.
Наконец, главная новость - изменился механизм доступа к исходникам. Теперь посетителям сайта предлагается для скачивания zip-архив (по одному архиву для каждого из языков), содержащий все необходимые для работы файлы: алгоритм, используемые им модули, библиотеку AP, тесты и примеры (если они есть). Следует отметить, что раньше транслятор генерировал фрагменты кода - работоспособные, но не являющиеся готовым к использованию модулем. Эти фрагменты требовалось вручную вставлять в проект, а если алгоритм использовал в своей работе вспомогательные алгоритмы, то требовалось скачивать не один, а несколько фрагментов кода и вручную сводить их воедино. Теперь транслятор генерирует готовые модули - со всеми необходимыми заголовочными файлами, uses/include и т.д. Как я надеюсь, эти нововведения облегчат работу с сайтом и использование программ.
P.S. Относительно планов на будущее: в настоящее время я думаю главным образом о тестировании и лицензировании, ну и о раскрутке англоязычного зеркала, само собой. Ждите новостей!
31.01.07 С момента последнего сообщения в ленте новостей прошло немало времени. Кое кто из посетителей даже подумал, что сайт умер. Спешу вас всех порадовать - библиотека алгоритмов жива :) Большую часть этого времени над сайтом велась работа, которая принесла два результата. Первый результат - на сайт добавлены исходники на C#. Второй результат - открыто английское зеркало ALGLIB.NET, на котором размещена часть материалов. Переведено на английский далеко не всё, но это - тот первый шаг, который было труднее всего сделать.
Кроме этого был ряд менее значительных изменений: добавлен экспериментальный раздел "операции с разреженными матрицами" (мне кажется, что эксперимент провалился по соображениям быстродействия), были ещё различные мелкие изменения на сайте. Однако, в этом выпуске речь пойдет не о том, что было раньше, а о моих дальнейших планах. Я думаю, что посетителям сайта будет интересно услышать о них.
Прежде всего, обрисую ситуацию с сайтом, как её вижу я. Первоначально этот сайт начинался как учебно-информационный проект. Он был библиотекой алгоритмов в полном смысле этого слова - библиотекой не сколько программ, сколько описаний. Со сменой автора сменился и подход - в отличие от Владимира Быстрицкого, я выбрал основным направлением программы. Таким образом, сайт называется "Библиотека алгоритмов" исключительно в силу традиции - сейчас это скорее библиотека реализаций, чем алгоритмов. Изменилась ниша сайта - теперь он позиционируется, как набор готовых решений для решения профессиональных, практических, а не учебных задач. Таким образом, направление развития сайта постепенно менялось, и сейчас сайт нуждается в существенной переработке, чтобы он соответствовал тому уровню, на который претендует.
Основные направления развития сайта на 2007 год.
1. Развитие англоязычного зеркала. На данный момент англоязычное зеркало нуждается как в пополнении материалами, так и в том, чтобы занять достойное место в результатах поисковиков. Зачем делать что-то, если этим никто не пользуется?
2. Решение вопроса с лицензированием. Условия, на которых сейчас распространяются программы с сайта, довольно-таки расплывчатые (если не сказать больше). После некоторых размышлений я пришел к выводу, что оптимальным вариантом была бы тройная open source лицензия - MPL/GPL/LGPL. Для этого требуется получить разрешение владельцев авторских прав на программы.
3. Тестирование. Алгоритмы на сайте нуждаются в тестировании. Они уже протестированы, но в ряде случаев требуются более глубокие тесты. Требуется механизм автоматического тестирования - сайт слишком большой, чтобы я вручную проверял каждый алгоритм в каждом из языков программирования.
4. Транслятор AlgoPascal. Хотя транслятор работает без сбоев (все последние баги, которые были замечены, находились именно в алгоритмах, а не в трансляторе), его архитектура нуждается в очередной переработке. Очередное расширение языка AlgoPascal оказалось невозможным из-за ограничений используемого парсера (оказывается, Yacc нереентерабелен - я просто в шоке).
5. Сайт. В переработке нуждается сам сайт. Например, механизм доступа к исходникам просто требует, чтобы его улучшили - вместо десятка ссылок на различные фрагменты исходного кода должна быть одна ссылка на архив, который содержит всё, что нужно, в готовой к включению в проект форме.
Подводя итог. По пункту 1 работа уже идет, на очереди пункт 3. Что из остального делать в первую очередь, разберемся по ходу дела (при этом у пункта 5 большие шансы вырваться в лидеры гонки). Важно то, что список приоритетных задач не включает в себя добавление на сайт новых исходников. Хотя есть ещё много направлений, которые на сайте совершенно не представлены, да и то, что представлено, всегда можно углубить, но сейчас пора остановиться и попытаться привести в порядок то, уже есть, а не искать что-то новое. Таким образом, в 2007 году появление на сайте новых алгоритмов маловероятно (разве что во второй половине года).
Ну и ещё - может, в этом году я всё же постараюсь возродить традицию ежемесячных выпусков новостей :)
09.04.06 Анонсированные ранее планы по добавлению на сайт алгоритмов, работающих с комплексными матрицами, реализованы. В разделе "операции с матрицами и векторами" появился подраздел операции с комплексными матрицами, в котором представлен следующий набор подпрограмм: LU-факторизация, обращение матрицы, вычисление определителя, оценка числа обусловленности. Также появился алгоритм для решения системы линейных уравнений с комплексными коэффициентами. Соответственно, обновилась стандартная библиотека AP, которую необходимо скачать с сайта для того, чтобы использовать новые исходники.
Изначально предполагалось реализовать и другие алгоритмы, оперирующие с комплексными матрицами (алгоритмы ортогональной факторизации, сингулярного разложения, поиска собственных значений), однако нехватка времени вынудила меня ограничиться только указанным выше набором, включающим в себя наиболее часто используемые алгоритмы.
Из других новостей следует отметить появление среди методов оптимизации L-BFGS-B-алгоритма, решающего задачу нелинейной оптимизации с простыми ограничениями на переменные, и алгоритма Левенберга-Марквардта, который может использоваться как для задач оптимизации, так и для аппроксимации нелинейным методом наименьших квадратов. Алгоритмы аппроксимации линейным МНК подверглись улучшению: вместо использования метода нормальных уравнений, который плохо себя проявляет в ряде случаев, в них теперь применяется сингулярное разложение, которое позволяет получить более качественные решения в случае плохо обусловленных базисов. Сам интерфейс алгоритмов не изменился, изменению подверглась только внутренняя часть
Относительно дальнейших планов. В не слишком отдаленном будущем я планирую продолжить работу над алгоритмами линейной алгебры, оперирующими с комплексными матрицами, однако это среднесрочная перспектива. В краткосрочной же перспективе все мое внимание поглощает один проект, о котором я сообщу после его реализации. Таким образом, в ближайшие несколько месяцев обновления на сайте маловероятны, поскольку проект, над которым я сейчас работаю, предусматривает развитие сайта в совершенно новом направлении, не связанном с добавлением на сайт новых алгоритмов.
07.02.06 Перенос алгоритмов из LAPACK продолжается. Теперь настала очередь алгоритмов решения задачи собственных значений. Перенесены алгоритмы решения симметричной вещественной задачи собственных значений (QL/QR-алгоритм) и решения несимметричной вещественной задачи собственных значений (QL/QR-алгоритм с множественными сдвигами). Также перенесены алгоритмы бисекции и обратной итерации для получения части собственных векторов и значений матрицы и алгоритм, решающий обобщенную симметричную положительно определенную задачу собственных значений.
Продолжается работа над алгоритмами линейной алгебры: был оптимизирован алгоритм сингулярного разложения (оптимизация коснулась эффективности работы на больших матрицах, не помещающихся в кэш процессора), проведены некоторые другие оптимизации. Также исправлена ошибка в коде подпрограммы, генерирующей элементарные вращения.
В разделе интегрирование функций появились три новые подпрограммы, позволяющие генерировать квадратуры Гаусса, квадратуры Гаусса-Лобатто и квадратуры Гаусса-Радау по коэффициентам рекуррентной последовательности ортогональных полиномов, порожденной весовой функцией квадратурной формулы.
По просьбам посетителей в язык AlgoPascal добавлен новый вид документирующих комментариев. Теперь в коде, доступном для скачивания, комментарии сопровождают не только подпрограмму в целом, но и отдельные фрагменты кода внутри неё, что позволяет легче разбираться в исходном коде. Исходники на сайте постепенно оформляются в соответствии с новым форматом.
В планах на ближайшее время - добавление версий подпрограмм линейной алгебры для комплексных матриц. В перспективе - помещение в открытый доступ транслятора AlgoPascal и описания языка.
10.10.05 Новости за сентябрь задержались на десять дней. Можно было бы сделать выпуск вовремя, но выкладывать на сайт неполную версию разделов "решение систем линейных уравнений" и "операции с матрицами", в которой новые исходники перемежаются со старыми, не хотелось - а если не выкладывать, то в выпуске новостей просто было нечего писать. Но теперь всё, что я хотел успеть сделать до конца сентября, уже сделано, так что можно сообщить о результатах.
Наибольшему изменению подвергся раздел Операции с матрицами и векторами. Из библиотеки LAPACK перенесен ряд подпрограмм. Для трех классов матриц (общего вида, симметричных и положительно определенных симметричных) перенесены подпрограммы факторизации (LU/LDLT/Холецкого), обращения, вычисления определителя и оценки числа обусловленности. Для матриц обшего вида также пересены алгоритмы QR- и LQ-разложения, и новый, более функциональный и надежный, алгоритм SVD-разложения.
Для тех, кто знает, что такое "блочно-матричные алгоритмы", сообщаю, что эти алгоритмы не были перенесены из LAPACK из-за технических сложностей. Все перенесенные алгоритмы являются Level 2 BLAS версиями. Возможно, в будущем часть алгоритмов будет перенесена из LAPACK именно в блочно-матричных версиях, оптимизирующих работу с кэшем процессора, но пока придется наслаждаться только обычными версиями, без оптимизации работы с кэшем.
Раздел Решение систем линейных уравнений также подвергся модификации. Часть алгоритмов была классифицирована, как устаревшие, появились новые алгоритмы - на основе LU-разложения (для систем общего вида) и на основе разложений Холецкого и LDLT (для систем с симметричными матрицами).
Анонсированные ранее планы по ускорению базовых операций линейной алгебры частично реализованы - в библиотеку AP для С++ добавлены подпрограммы, ускоряющие линейные операции с векторами, столбцами и строками матриц (аналог Level 1 BLAS) за счет развертки циклов и использования указателей для доступа к внутренней памяти матриц. Как мне кажется, теперь быстродействие линейных операций находится на максимальном достижимом без использования SSE (или его аналогов) уровне.
Относительно оптимизации исходников на Delphi пока ничего сказать не могу. В Delphi реализован крайне неэффективный механизм работы с многомерными массивами, так что быстродействие алгоритмов линейной алгебры могло бы быть раз в пять выше, и оптимизация безусловно нужна. Вместе с тем, вряд ли в ближайшее время у меня найдется время на эту работу. Ну а оптимизация программ на Visual Basic... этот язык изначально не предназначен для скоростных вычислений, так что здесь и речи быть не может о какой-либо оптимизации, кроме алгоритмической.
Таким образом, на данный момент С++ версии алгоритмов линейной алгебры являются самыми скоростными из представленных на сайте. Следом за ними идет Delphi, отставая в несколько раз (точная величина отставания зависит от используемого компилятора С++), а Visual Basic скромно плетется в конце. Надеюсь в ближайшее время сравнить быстродействие алгоритмов линейной алгебры на разных компиляторах и в разных ситуациях, и представить общественности результаты.
Ну и последняя новость - проведен очередной редизайн сайта. У меня пока нет времени провести всесторонную проверку нового дизайна в различных браузерах (я не профессиональный дизайнер, так что у меня установлен только IE), если кто-то из посетителей заметит баги в новом дизайне, просьба сообщить об этом мне.
01.09.05 Новости за август (я все-таки не забыл про ежемесячный выпуск!). Сообщаю, что перевод библиотеки специальных функций Cephes практически закончен. На данный момент раздел "специальные функции" содержит 50 файлов с исходными кодами, из них 37 получены путем перевода исходных кодов из библиотеки Cephes.
В библиотеке осталось ещё девять файлов, которые представляют интерес, но пока я беру таймаут и на некоторое время завязываю со специальными функциями. Сколько времени можно заниматься одним и тем же, в конце концов? На данный момент в сфере моих интересов - линейная алгебра.
Работы ведутся в двух направлениях. Во-первых, это перенос и адаптация исходных кодов из библиотеки LAPACK. Сделано немало, и я расчитываю уже в сентябре выложить в открытый доступ переработанную, улучшенную версию разделов "решение систем линейных уравнений", "операции с матрицами" и "поиск собственных чисел и векторов". В дальнейшем планируется перевод ряда исходных кодов, оперирующих с ленточными матрицами и прочими матрицами специального вида.
Второе направление работы - это повышение эффективности базовых операций линейной алгебры. На данный момент все операции типа "вектор+вектор", "вектор-вектор" и т.д. осуществляются путем записывания прямо в алгоритме цикла for, реализующего их. При этом не учитываются особенности этих операций (последовательное расположение в памяти элементов, составляющих операнды, и возможность развертки циклов), позволяющие значительно повысить быстродействие даже без оптимизации под конкретный процессор. В скором времени эти недостатки будут исправлены.
01.08.05 Недавно мне пришла в голову замечательная идея - а почему бы мне не взять за правило делать ежемесячные выпуски новостей? Идея понравилась, и я решил делать их 26-ого числа каждого месяца. Хорошее число - дважды тринадцать. Не простое, но и не слишком сложное - произведение двух простых. Когда я вспомнил об этой идее вечером 27-ого, было уже поздно, поэтому я решил делать выпуски новостей первого числа каждого месяца. К сожалению, сейчас уже началось второе, но так как я начал писать этот выпуск первого числа, то в нем будет стоять именно эта дата.
Итак, ещё один выпуск новостей после долгого молчания. За эти три месяца на сайте появился ряд новых алгоритмов.
Прежде всего, изменениям подвергся раздел "Специальные функции". В него были перенесены алгоритмы из раздела "Ортогональные полиномы", поскольку я решил, что в первую очередь ортогональные полиномы - это специальные функции, и только во вторую - полиномы. Также в раздел было добавлено 17 новых алгоритмов вычисления специальных функций из свободно распространяемой библиотеки математических функций Cephes, разработанной Стивеном Мошером. У имеющихся алгоритмов добавлена справка о точности вычисления функции - необходимая составляющая, которая раньше отсутствовала. Работы по переводу Cephes идут полным ходом, остается около двух десятков алгоритмов, которые я расчитываю перенести в ближайшее время.
Теперь коротко про обновления в других разделах.
В общем, такие вот результаты. Несмотря на то, что по несколько месяцев лента новостей не обновляется, сайт живет и развивается. Кстати: непосредственно сейчас кроме обычной работы по развитию сайта реализуется один очень интересный проект, который я надеюсь в скором времени анонсировать.
03.05.05 За прошедшие месяцы на сайте произошел ряд обновлений, о которых я сообщу в отдельном выпуске. На сегодня главная новость - объединение библиотеки алгоритмов и проекта SOURCES.RU. Думаю, оба проекта только выиграют от этого объединения.
Как вы можете видеть, сайт сменил доменное имя с alglib.manual.ru на alglib.sources.ru. Соответственно, сменилась ссылка на форум (ранее она показывала на форум алголиста). Пока что это единственные изменения, если не считать обновившегося дизайна. В вопросе о дальнейших изменениях в связи с переездом нет ясности. Ряд проблем технического и концептуального плана стоит на пути простого слияния двух проектов в один. Думаю, в будущем граница между sources.ru и alglib.sources.ru будет постепенно стираться, но к чему мы в итоге придем, покажет лишь время. Делать какие-либо далеко идущие прогнозы сейчас невозможно.
Сообщаю вам о переезде и приглашаю посетить сайт на новом месте. На сегодня всё.
08.03.05 Четыре месяца прошло с последнего выпуска новостей. По отсутствию новостей можно было бы решить, что проект опять ударился в спячку, но... но это было бы неправильным решением. В корне неправильным. Проект развивался, но силы заканчивались как раз тогда, когда надо было писать об этом в рассылку новостей.
За эти четыре месяца произошло много чего. Я начал работать (вот она, причина снижения активности), и даже ухитрился сдать сессию на отлично, не переставая работать. За что (я про сдачу сессии на отлично) хочу выразить горячую благодарность нашему правительству и президенту В.В.Путину лично - их решение о создании "новогодних каникул" оказало мне гигантскую помощь в сдаче сессии. Как бы я ещё получил десяток свободных от работы дней на подготовку к экзаменам? Когда президент подписал-таки указ, моя благодарность к нему достигла исторического максимума за все четыре с половиной года его правления.
Да, никто не слышал, у нас в июне никаких праздников не планируется вводить? А то у меня ещё летняя сессия впереди...
В общем, закончили с политикой, вернемся к математике. За эти четыре месяца на сайте даже появилась ещё одна порция алгоритмов, о чем я и сообщаю.
Грядут и дальнейшие обновления, после того, как я всё-таки переведу L-BFGS алгоритм многомерной минимизации. Раздел "поиск экстремумов функций" сейчас практически не развит, но в скором времени он пополнится несколькими исходниками, которые кроме как на Фортране или в составе проприетарного софта я больше нигде не видел.
24.10.04 Тема сегодняшнего выпуска - изменение дизайна и функциональности сайта. Улучшения в дизайне не так уж велики: несколько изменилась цветовая схема, меню перенесено в верхнюю часть окна, изменилась разбивка текста. Гораздо интереснее (и важнее) изменения в функциональности.
Во-первых, обновилась стандартная библиотека AP. Теперь она обзавелась более-менее нормальной документацией, а версия для С++ была существенно переработана, став ещё более удобной для использования. Также была исправлена пара ошибок.
Во-вторых, изменился способ работы с массивами в языке Delphi. Раньше для этого использовались классы, которые позволяли имитировать динамические массивамы, нумерация которых начинается с произвольного числа, а не с 0, как принято в Delphi. Я долгое время размышлял, правильно ли это, и решил, что нет. Стандартные массивы куда удобнее в использовании, а то, что некоторые алгоритмы начинают нумерацию с 0, а не с 1, не должно быть большой проблемой. Просто элементы, лежащие в начале массива, не будут использоваться.
Изменился способ скачивания алгоритмов с сайта. Раньше для скачивания, скажем, версии на Delphi, приходилось открывать в браузере отдельное окно. Сейчас все ссылки для скачивания находятся на странице алгоритма, т.е. не надо открывать отдельных окон. Посетителю предоставляется выбор: он может скачать исходный код алгоритма и сохранить его на локальной машине, а может просмотреть в окне браузера. Как мне кажется, такой подход более удобен.
Следующее улучшение - учет взаимосвязей между алгоритмами. Для примера можно рассмотреть алгоритм вычисления обратной неполной гамма-функции. В ходе расчетов он использует алгоритмы вычисления логарифма гамма-функции, неполной гамма-функции, обратной интегральной функции вероятности нормального распределения. Эти алгоритмы тоже надо скачать с сайта. Раньше для этого требовалось перейти на страницы этих алгоритмов, теперь ссылки на них автоматически добавляются к ссылкам для скачивания алгоритма, который их использует. Т.е. весь требуемый код можно закачать с одной страницы.
На сайте появился FAQ. В нем можно выделить две части: рассказ о проекте в целом и разбор возникающих при использовании алгоритмов вопросов.
В общем, куча изменений, которые, я надеюсь, сделают сайт ещё более удобным для посетителей.
23.10.04 На сайте очередное обновление, а также исправлена очередная порция ошибок. Сначала про ошибки.
Теперь про обновления.
Наконец, на сайте появился новый раздел: Квадратурные формулы Гаусса. Здесь находятся следующие исходники:
Также существенно изменились дизайн и функциональность сайта, но об этом - в следующем выпуске.
23.09.04 Я хотел написать в этом выпуске об исправленных ошибках на сайте и рассказать о новых алгоритмах, но придется поговорить о менее приятных вещах. Эта проблема возникла не как-то вдруг, в неявной форме она назревала уже давно, но только сейчас я заговорил о ней.
За последние несколько дней практически одновременно я получил от посетителей целую серию однотипных писем с сообщениями об ошибках в алгоритмах, которые и побудили меня к написанию этого выпуска. Их содержание было одинаковым - "алгоритм X не работает, потому что переменная Y в ходе цикла не меняет свое значение". Я не называю имен алгоритмов и переменных, потому что каждый раз это были разные алгоритмы и разные переменные. Тем не менее, была одна общая черта - два из трех алгоритмов не имели исходников на AlgoPascal, только блок-схему. А в третьем случае посетитель изучал алгоритм по блок-схеме, а не по исходному коду.
Причина была проста - блок-схема это не программа, а рисунок, который можно сделать программой. Код, изменяющий переменную цикла, присутствовал в каждом из исходников - просто он находился в самом конце прямоугольника с телом цикла. И если размер прямоугольника оказывался чуть-чуть меньше видимого размера кода, то часть кода - самая последняя строчка - исчезала из поля зрения. Хотя она присутствовала в экспотированном паскалевском коде, но при просмотре блок-схемы её не было видно.
Я оказался в затруднительном положении. С одной стороны, поддержка блок-схем сейчас приостановлена. Владимир Быстрицкий - автор редактора блок-схем - сейчас сайтом не занимается, а у меня хватает своих заморочек с AlgoPascal. С другой стороны, не дело держать на сайте вводящую посетителей в заблуждение информацию. С третьей стороны, блок-схемы должны остаться на сайте по-любому. С четвертой, у меня нет времени на кропотливое изучение картинок с ромбиками и квадратиками с целью последующего редактирования. У меня просто нет сил на исправление ошибок в блок-схемах, поскольку эта работа лишь на 5% состоит в написании кода, а на 95% - в размещении на экране квадратиков и соединительных линий.
Я решил поступить следующим образом. До сегодняшнего дня блок-схемы находились на сайте в виде GIF-файлов и в виде BLS-файлов. С сегодняшнего дня GIF-файлы с сайта исчезают, поскольку по ним в принципе невозможно определить, весь ли код попал в узенький прямоугольник на блок-схеме. BLS-файлы остаются, поскольку там можно найти недостающие фрагменты, но редактировать их и исправлять ошибки в BLS-версиях алгоритмов я больше не буду.
Рядом с ссылкой для скачивания BLS-файлов будет предупреждение пользователям о том, что поддержка BLS прекращена на неопределенный срок, и что ошибки в BLS-версиях алгоритмов не исправляются.
Мне крайне неприятно принимать такое решение, ведь блок-схемы сделали этот сайт тем, чем он сейчас является, но у меня не осталось другого выбора. Я рассматривал различные способы решения этой проблемы, главный из которых - написание конвертера из AlgoPascal в BLS, но пока эта проблема не решена, я не буду замалчивать её.
07.09.04 Основная беда всех проектов, которые держатся исключительно на энтузиазме авторов - у авторов не хватает времени на их обновление. За прошедшие четыре месяца библиотека алгоритмов столкнулась с принципиально новой напастью - у меня не находилось времени на написание выпуска новостей :) А писать было про что.
В общем, вываливаю список всех изменений:
Список новых исходников на сайте:
23.04.04 Моя дипломная работа продолжает поглощать почти всё мое внимание, но мне иногда удается находить время на сайт. Итак, очередные обновления.
Новость первая - на сайте появилась новая статья, посвященная численному интегрированию функций. Автор статьи - AQL - в данный момент ведет работу над статьей о несобственных интегралах. Также вместе со статьей поступили исходники целого ряда классических методов (ссылки в самой статье)
Новость вторая - исправлены ошибки в алгоритмах. Это ошибка в алгоритме QR-разложения (за информацию спасибо Виталию) и в интеграле методом Симпсона от функции, заданной таблично (про ошибку сообщила Евгения).
Новость третья - на сайте появилась новая порция алгоритмов:
Изменения произошли в следующих разделах:
Как всегда, остается некоторое количество исходников, которые я ещё не выложил на сайт, и, как всегда, я надеюсь проделать это как можно быстрее.
09.03.04 Последние полтора-два месяца, увы, я был сильно занят. В результате уже пару недель на сайте лежит обновление, а выпуска новостей всё нет и нет. Вот такой вот непорядок. Теперь время нашлось и я сообщаю об изменения на сайте
Изменения произошли в следующих разделах:
Исправлена ошибка в алгоритме интерполяции сплайном, за что спасибо посетителю totev. Ошибка довольно-таки коварная, поскольку проявлялась лишь при числе точек, равном двойке - произошла она во время переделки алгоритма (см. ниже).
Также следует отметить, что у ряда алгоритмов появились аннотации (небольшие комментарии под названием алгоритма), а в разделах "Интерполяция" и "Решение уравнений" была проведена работа над "приведением алгоритмов к единому знаменателю", т.е. алгоритмы, решающие схожие задачи, стали принимать данные в одной и той же форме. До этого существовал некоторый разнобой - скажем, интерполяция полиномом требовала нумерации точек от 0 до N, а интерполяция сплайном - от 1 до N - что приводило к путанице.
На подходе существенное обновление раздела "Собственные числа и вектора".
14.01.04 Сегодня на сайте произошли следующие события... вообще-то, произошли они вчера, но писать в 2 часа ночи выпуск новостей не хотелось, так что будем делать вид, что всё произошло сегодня :) Итак, новости.
Новость первая - на сайте появилась подсветка синтаксиса. Раскрашиваются как полученные в результате трансляции исходники алгоритмов, так и оригинальный код на AlgoPascal. Для раскраски исходников на Delphi, C++ и AlgoPascal выбрана цветовая схема сред разработки Delphi/Builder, исходники на Visual Basic раскрашены в соответствии с цветовой схемой Visual Studio 6.0 Вообще, эта мысль назревала давно, но довести серверную версию транслятора до нужной кондиции я собрался только на этой неделе.
Вторая новость - на сайт выложена ещё одна порция алгоритмов:
9.01.04 Новости на сегодня: обновления в разделах Решение систем линейных уравнений и Поиск экстремумов функций.
Сначала о линейных уравнениях. Во-первых, переведен на AlgoPascal метод вращений - теперь этот алгоритм доступен не только в виде блок-схемы, но и в виде исходников на трех языках программирования. Во-вторых, появились новые алгоритмы с "продвинутой" функциональностью: метод ортогонализации (и его улучшенный вариант), позволяющие решать недоопределенные и переопределенные системы уравнений (т.е. где число неизвестных неравно числу уравнений) в том числе и с вырожденной матрицей, и метод SVD-разложения, ищущий не только частное решение системы, но и фундаментальную систему решений.
В разделе Поиск экстремумов функций исправлены ошибки в алгоритме поиска методом конфигураций, исправленный исходник прислал Stas.
30.12.03 Сегодня на сайте пополнение, появился новый раздел - специальные функции. Здесь вычисление гамма-функции, функций Бесселя и так далее. Раздел возник благодаря Александру Пирогову, приславшему "стартовый капитал" в виде библиотеки на Delphi. На данный момент раздел состоит исключительно из его исходников, но в будущем надеюсь расширить список представленных алгоритмов.
Также исправлена ошибка в алгоритме интегрирования методом прямоугольников с оценкой точности. Именно оценка и работала неправильно (слишком уж осторожно), но теперь ошибка исправлена, за что спасибо Борису Швацману. Ещё одна ошибка обнаружена в алгоритме поиска методом Кнута-Морриса-Пратта - нашел её Виктор Kerby. Остальные вопросы я, скорее всего, решу уже в январе.
7.12.03 Сайт наконец-то открылся. Полностью реализована задуманная функциональность, полностью перенесено содержимое со старого сайта.
10.11.03 Сайт доступен в режиме "under construction".
|
ALGLIB project, 1999-2010 |