параллельные вычисления и Гаусс

Например, можно эффективно использовать векторные операции, т.е. оперировать сразу со строками. Что-то типа первую строку умножить на число и вычесть из второй. А операции со строками уже параллелятся, покомпонентно.

Короче, переписать алгоритм, по максимуму используя векторные операции, как в фортране 90 или матлабе. Кстати, хорошие компиляторы фортрана такие вещи сами хорошо параллелят, собственно, векторный синтаксис для этого и придуман.

Другой вариант -- взять какой-нибудь другой прямой метод, что-нибудь в духе декомпозиции области.

Посмотри еще книгу Голуб, Ван Лоун, Матричные вычисления, http://www.book.ru/cgi-bin/book.pl?page=4&book=27895, там что-то есть про распараллеливание.