Iterative Template Library

Iterative Template Library (ITL) — библиотека компонентов, предназначенных для применения итеративных численных методов в манипуляциях с объектами линейной алгебры.

ITL состоит из двух функциональных групп. Первая группа представляет собой коллекцию сложных итеративных методов, использующих алгоритмы базовых операций линейной алгебры, реализованные в специализированных пакетах типа Matrix Template Library (MTL) или Blitz++. Вторая группа — это набор алгоритмов предобуславливания, разработанный специально для работы с MTL.

Библиотека ITL использует абстрактные интерфейсы для операций вида матрица-вектор, вектор-вектор и вектор-скаляр, что позволяет прозрачно использовать их реализацию в сторонних библиотеках.

Данная библиотека была создана в Open Systems Lab — исследовательской лаборатории Индианского университета, как часть MTL.

Впервые была опубликована отдельно от MTL 25 июля 2000 года. Новый релиз включал в себя, кроме всего прочего, несколько интерфейсов для BLAS и Blitz++.

В последнем релизе (4.0.0) была произведена декомпозиция библиотеки на три функциональные области: методы для работы с подпространством Крылова; предобуславливания и интерфейсы. Методы для работы с подпространством Крылова являются базовыми, и не ограничены в использовании стандартными библиотеками, реализующими объекты линейной алгебры. Интерфейсы предназначены для использования в итеративных алгоритмах подпространства Крылова основных операций линейной алгебры, реализованных в сторонних библиотеках, таких как: MTL, Blitz++. Предобуславливания реализованы только для работы с библиотекой MTL.

Также, в этот релиз были включены экспериментальные интерфейсы для поддержки параллельных вычислений.

Идеи, заложенные в ITL, были продолжены и развиты в проекте Iterative Eigensolver Template Library (IETL)^[2].

Принципы обобщённого программирования, в рамках которых создана библиотека,^[3] предполагают упрощение интерфейсов. Это привело к тому, что алгоритмы ITL напоминают некий псевдокод. Как минимум, по сравнению с другими реализациями тех же алгоритмов. К примеру, реализация метода сопряжённых градиентов будет выглядеть следующим образом:

/* необходимые операции: mult,copy,dot_conj,add,scaled */
template < class Matrix, class VectorX, class VectorB, 
           class Preconditioner, class Iteration >
int cg(const Matrix& A, VectorX& x, const VectorB& b, 
       const Preconditioner& M, Iteration& iter)
{
    typedef VectorX TmpVec;
    typename itl_traits<VectorX>::value_type rho(0), rho_1(0), alpha(0), beta(0);
    TmpVec p(size(x)), q(size(x)), r(size(x)), z(size(x));
 
    itl::mult(A, itl::scaled(x, -1.0), b, r);	  
 
    while (! iter.finished(r))
    {
        itl::solve(M, r, z);
        rho = itl::dot_conj(r, z);
        if (iter.first())
            itl::copy(z, p);		  
        else 
        {
            beta = rho / rho_1;
            itl::add(z, itl::scaled(p, beta), p); 
        } 
 
        itl::mult(A, p, q);		  
 
        alpha = rho / itl::dot_conj(p, q);
 
        itl::add(x, itl::scaled(p, alpha), x);  
        itl::add(r, itl::scaled(q, -alpha), r); 
 
        rho_1 = rho;
 
        ++iter;
    }
 
    return iter.error_code();
}

• Matrix Template Library
• Blitz++
• Template Numerical Toolkit

• Домашняя страница проекта (англ.)