Нахождение наименьшего (разреженного) решения матричного уравнения
Я планирую решить СКВ стандартной формы Ax = b, в целых числах, используя LUP-разложение, используя только один поток.
A - это матрица размером примерно n3 × 2n3, n ≈ 100 (чем больше, тем лучше). Матрица действительно разреженная - в каждом столбце есть только 4 ненулевых элемента, и все они равны ±1, в каждом столбце максимум n ненулевых элементов. b также столбец с только 4 записями, равными ±1.
Таким образом, я могу получить одно решение, а затем я могу добавить к нему любую линейную комбинацию (с целым коэффициентом) векторов из ядра A, чтобы получить другое решение (я также понимаю, что основание этого ядра легко читается из матрицы U). Я хочу найти решение с max c⋅n ненулевых записей. Я знаю, что обычно существование такого решения не подразумевается (для фиксированного коэффициента с), но в моем случае я думаю, что должно быть одно (а не только одно). Вопрос: как мне это найти?
PS, если кто-то желает предоставить некоторые точные оценки для времени выполнения LUP-разложения + решающей части или также оценки для плотностей L, U, L \ b (решение Ly = b, стиль matlab) и mb даже LU \ b - Я также был бы очень благодарен. В качестве альтернативы, любая литература по этой теме также будет полезна.