Решение

У меня есть матрицы A и G . A является разреженным и имеет размер n × n с очень большим n (может быть порядка нескольких миллионов). G является матрицей высотой n × m с довольно небольшим m ( 1 < m < 1000 ), и в каждом столбце может быть только один 1 запись с остальным 0 «с, таким образом, что G T G = Я . А огромен, так что это действительно трудно инвертировать, и я могу решить линейную систему, такую ​​как $A$$G$$A$$n\times n$$n$$G$$n\times m$$m$$1 \lt m \lt 1000$$1$$0$$G^TG = I$$A$ A = b итеративно, используя метод подпространства Крылова, такой как B i C G S t a b ( l ) , но у меня нет A - 1 явно.$Ax = b$$\mathrm{BiCGStab}(l)$$A^{-1}$

Я хочу решить систему вида: ( G T A - 1 G ) x = b , где x и b - векторы длины m . Один из способов сделать это - использовать итерационный алгоритм в итерационном алгоритме, чтобы найти для A - 1 для каждой итерации внешнего итерационного алгоритма. Это было бы чрезвычайно дорого в вычислительном отношении, однако. Мне было интересно, есть ли в вычислительном отношении более простой способ решения этой проблемы.$(G^TA^{-1}G)x = b$$x$$b$$m$$A^{-1}$

Введем вектор y : = - A - 1 G x и решим большую связанную систему A y + G x = 0 , G T y = - b для ( y , x ) одновременно, используя итерационный метод. Если A симметричен (как представляется вероятным, хотя вы не указали это явно), то система является симметричной (но неопределенной, хотя и квазиопределенной, если $y:=-A^{-1}Gx$$Ay+Gx=0$$G^Ty=-b$$(y,x)$$A$$A$положительно определен), что может помочь вам выбрать подходящий метод. (релевантные ключевые слова: матрица ККТ, квазиопределенная матрица).

Редактировать: Как A является сложной симметричной, так и расширенная матрица, но нет квазиопределенности. Однако вы можете использовать й подпрограмму для вычисления А * х = ¯ ¯ х ; поэтому вы можете адаптировать метод, такой как QMR, ftp://ftp.math.ucla.edu/pub/camreport/cam92-19.pdf (разработанный для реальных систем, но вы можете легко переписать его для сложных систем, используя сопряженный в место транспонирования), чтобы решить вашу проблему.$A$$Ax$$A^*x=\overline{A\overline x}$

Edit2: На самом деле, (0,1) -структура G означает, что вы можете удалить x amd и компоненты G T y символически, таким образом получая меньшую систему для решения. Это значит возиться со структурой A и оплачивать только тогда, когда A задано явно в разреженном формате, а не как линейный оператор.$G$$x$$G^Ty$$A$$A$

Following Arnold's reply, there is something you can do to simplify the problem. Specifically, rewrite the system as $Ay+Gx=0, G^Ty=-b$. Then note that from the statement that $G$ is tall and narrow and each row has only one 1 and zeros otherwise, then the statement $G^Ty=-b$ means that a subset of the elements of $y$ have a fixed value, namely the elements of $-b$.

Let us say that for simplicity that $G$ has $m$ columns and $n$ rows and that exactly the first $m$ rows have ones in them and that be reordering the elements of $x$ I can make it so that $G$ has the $m \times m$ identity matrix at the top and a $n-m \times m$ zero matrix at the bottom. Then I can partition $y=(y_c,y_f)$ into $m$ "constrained" and $n-m$ "free" elements so that $y_c=-b$. I can also partition $A$ so that $A=\begin{pmatrix} A_{cc} & A_{cf} \\ A_{fc} & A_{ff} \end{pmatrix}$. From the equation $Ay+Gx=0$ I then get the following:

In other words, given the structure of $G$, solving the linear system you have is really not more difficult than solving a single linear system with $A$.

But we know $G$, $G^T$ and $A$, so

$G^T A^{-1} G x = b$

$G G^T A^{-1} G x = G b$

Since $G^T G = I$, then $G^T = G^{-1}$, so $G G^T=I$:

$A^{-1} G x = G b$

$A A^{-1} G x = A G b$

$G x = A G b$

$G^T G x = G^T A G b$

$x = G^T A G b$

Unless I've missed something, you don't need any iteration, or any solver to calculate x given $G$, $A$ and $b$.