Как лучше всего хранить коэффициенты?

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

а как потом такую матрицу загнать в любой из существующих методов решения СЛАУ - в этом вся и соль...

Любой метод можно подогнать под любой вид матрицы. Будет такой метод работать медленнее чем для обычной матрицы.
Как всегда: выигрываем во времени - проигрываем в памяти. Выигрываем в памяти - проигрываем во времени.

valeriikozlov, проект с полным объёмом памяти позволил получить решение за 10 секунд. Аналогичный алгоритм с поэлементной работой отрабатывал где-то по памяти за мин 25(как раз успевал кофейка выпить). (Правда ЭВМ для теста была паршивая ОЗУ 384 Мб и Celeron 1.1)

для хранения разреженных матриц методов много. одни сильно выигрывают по памяти, но уступают по скорости "распаковки", другие - наоборот.
если матрица у нас N*N и в ней k ненулевых элементов, то есть метод, позволяющий хранить 2*k значений для сохранения данных о матрице. алгоритм таков:

пусть дана матрица:
0 0 3 0 0
1 0 2 0 0
0 0 0 0 4
0 5 0 1 0
0 0 0 0 1
Заведем массив Values, в котором перечислим все значения, выбрав определенный способ обхода (по столбцам, к примеру).
Values={1,5,3,2,1,4,1}
Теперь заведем массив Coords, элементами которого будет значение i+(j-1)*n, где i-номер строки, j-номер столбца элемента из массива Values, а n-порядок матрицы. Проще говоря порядковый номер при выбранном виде обхода. Получим:
Coords={2,9,11,12,19,23,25}

Соответственно, для проверки возьмем произвольные координаты элементов: (3;4) и (4;2). Подставляем в формулу выше и получаем значения 18 и 9. Ищем эти значения в массиве coords. 18 не найдено, значит элемент нулевой. 9 найдено, значит элемент не нулевой. Берем индекс этого значения в Coords - под этим же номером в Values будет храниться значение.

Если матрица симметричная, то алгоритмы еще интереснее. А если к тому же и ленточная (все ненулевые элементы близко к диагонали), то там крайне эффективные схемы хранения есть.