<p>When they solve <span class="math-container">$Av=-b$</span> the assumption is that <span class="math-container">$A$</span> is non-singular. Whenever <span class="math-container">$A$</span> is singular the problem can either have no solution, or infinitely many solutions. In their case I believe it is the latter. Remember that <span class="math-container">$v = (p,s)$</span>. What they say is that they set the solution for <span class="math-container">$p$</span> to be the edge midpoint: <span class="math-container">$p=\frac{p_1+p_2}{2}$</span> and then plug that into the equation to reduce the system:
<span class="math-container">\begin{align}
-b = Av \iff -\begin{bmatrix} b_1\\ b_2\end{bmatrix} =
\begin{bmatrix}
A_{11} &amp; A_{12}\\
A_{21} &amp; I
\end{bmatrix}
\begin{bmatrix}
p \\ s \end{bmatrix} =
\begin{bmatrix} A_{11} \\ A_{21}\end{bmatrix}p+ \begin{bmatrix} A_{12} \\ I \end{bmatrix} s.
\end{align}</span>
If you assume the system is consistent, then <span class="math-container">$s = -b_2 - A_{21}p$</span>. If the system is inconsistent, then you can try to find the solution that least violates it as:
<span class="math-container">$$(A_{12}^TA_{12}+I)s = -A_{12}^T(b_1+A_{11}p) - (b_2+A_{21}p).$$</span>
I suppose the system ought to be consistent though.</p>
<p>Edit:</p>
<p>Here's a more general approach as to how you can factorize such problems if you assume <span class="math-container">$A_{22}$</span> is an invertible matrix (it is essentially block Gaussian elimination):</p>
<p><span class="math-container">\begin{align}
\begin{bmatrix} b_1 \\ b_2\end{bmatrix} &amp;=
\begin{bmatrix}
A_{11} &amp; A_{12} \\ A_{21} &amp; A_{22}
\end{bmatrix}
\begin{bmatrix}
x_1\\ x_2
\end{bmatrix}
\\
\begin{bmatrix}
b_1 \\ b_2 
\end{bmatrix}
&amp;= \begin{bmatrix}
A_{11}x_1 + A_{12}x_2 \\
A_{21}x_1 + A_{22}x_2
\end{bmatrix}
\\
\begin{bmatrix}
b_1\\ 
A_{22}^{-1}(b_2 - A_{21}x_1)
\end{bmatrix} 
&amp;=
\begin{bmatrix}
A_{11}x_1 + A_{12}x_2
\\
x_2
\end{bmatrix} 
\\
\begin{bmatrix}
b_1 - A_{12}A_{22}^{-1}b_2 \\
A_{22}^{-1}(b_2 - A_{21}x_1)
\end{bmatrix}
&amp;=
\begin{bmatrix}
(A_{11}-A_{12}A_{22}^{-1}A_{21})x_1 \\ x_2
\end{bmatrix}
\end{align}</span></p>
<p>In your case <span class="math-container">$A_{22} = I$</span> so the inverse is just <span class="math-container">$I$</span>. If the Schur complement <span class="math-container">$[A/A_{22}]= A_{11}-A_{12}A_{22}^{-1}A_{21}$</span> is invertible, then
<span class="math-container">$$x_1 = [A/A_{22}]^{-1}(b_1 - A_{12}A_{22}^{-1}b_2), \quad x_2 = b_2 - A_{21}x_1.$$</span></p>
<p>But it could happen that the Schur complement is not invertible. If <span class="math-container">$b_1 - A_{12}A_{22}^{-1}b_2$</span> is in the range of <span class="math-container">$[A/A_{22}]$</span> you have infinitely many solutions, since if <span class="math-container">$x_1^*$</span> is a solution, and <span class="math-container">$w$</span> is a non-zero vector from the kernel of <span class="math-container">$[A/A_{22}]$</span>, then also <span class="math-container">$x_1^* + \alpha w$</span> is a solution.
Having one such solution <span class="math-container">$x_1^*$</span> you can compute <span class="math-container">$x_2^* = b_2 - A_{21}x_1^*$</span>. In the paper they set <span class="math-container">$x_1^* = \frac{p_1+p_2}{2}$</span>. I haven't proven that this is necessarily a solution for their matrix though.</p>
<p>The other case is that <span class="math-container">$b_1 - A_{12}A_{22}^{-1}b_2$</span> is
not in the range of <span class="math-container">$[A/A_{22}]$</span>. Then there are no solutions. But you can try for the closest thing to a solution in an <span class="math-container">$L_2$</span> sense. Then <span class="math-container">$$x_1^+ = [A/A_{22}]^+(b_1 - A_{12}A_{22}^{-1}b_2),$$</span>
where <span class="math-container">$[A/A_{22}]$</span> is the Moore-Penrose inverse. You may again set <span class="math-container">$x_2 = b_2 - A_{21}x_1^+$</span>.</p>

CC BY-SA 4.0
2024-10-30T22:53:23.740Z
2024-10-31T10:04:40.567Z
2024-10-31T10:04:40.567Z
lightxbulb
<p>I am reading the new qem paper for mesh simplification with attributes.</p>
<p>On page 5 one encounters this paragraph:</p>
<p><a href="https://i.sstatic.net/DaQCCwQ4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DaQCCwQ4.png" alt="enter image description here" /></a></p>
<p>The extended form of equation (2) referred to by the paper looks like this:
<span class="math-container">$$Ax = -b$$</span></p>
<p>Where <span class="math-container">$A, b$</span> are this:</p>
<p><a href="https://i.sstatic.net/DdYemyP4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DdYemyP4.png" alt="enter image description here" /></a></p>
<p>I am not fully understanding how to get the attribute simplification in the case of an ill-conditioning. Basically, I don't understand what &quot;the remaining system&quot; should look like.</p>
<p>At face value, setting <span class="math-container">$p$</span> to a constant, means that your unknown vector has 3 less rows, but you can;t just truncate <span class="math-container">$A, b$</span> because then you have an under-constrained system. Since the paper only specifies that one sentence, I am at a loss as to what to do here.</p>

CC BY-SA 4.0
2024-10-31T09:47:46.023Z
I updated my answer. The method described should also make it easier to solve the system, since now you need only a $3\times 3$ (pseudo-)inverse.
lightxbulb
<mathematics><computational-geometry><geometry><mesh><matrix>
New QEM, question about degenerate case
Makogan
# New QEM, question about degenerate case

(Asked by: username_0 on 2024-10-30)

I am reading the new qem paper for mesh simplification with attributes.

On page 5 one encounters this paragraph:

[![enter image description here](https://i.sstatic.net/DaQCCwQ4.png)](https://i.sstatic.net/DaQCCwQ4.png)

The extended form of equation (2) referred to by the paper looks like this:
$$Ax = -b$$

Where $A, b$ are this:

[![enter image description here](https://i.sstatic.net/DdYemyP4.png)](https://i.sstatic.net/DdYemyP4.png)

I am not fully understanding how to get the attribute simplification in the case of an ill-conditioning. Basically, I don't understand what "the remaining system" should look like.

At face value, setting $p$ to a constant, means that your unknown vector has 3 less rows, but you can;t just truncate $A, b$ because then you have an under-constrained system. Since the paper only specifies that one sentence, I am at a loss as to what to do here.

**Tags:** mathematics, computational-geometry, geometry, mesh, matrix

> **Comments:**
> **username_1**: I updated my answer. The method described should also make it easier to solve the system, since now you need only a $3\times 3$ (pseudo-)inverse.  

---

## 1 answers

### Answer by username_1 on 2024-10-30. Score: 3 | Accepted answer

When they solve $Av=-b$ the assumption is that $A$ is non-singular. Whenever $A$ is singular the problem can either have no solution, or infinitely many solutions. In their case I believe it is the latter. Remember that $v = (p,s)$. What they say is that they set the solution for $p$ to be the edge midpoint: $p=\frac{p\_1+p\_2}{2}$ and then plug that into the equation to reduce the system:
\begin{align}
-b = Av \iff -\begin{bmatrix} b\_1\\ b\_2\end{bmatrix} =
\begin{bmatrix}
A\_{11} & A\_{12}\\
A\_{21} & I
\end{bmatrix}
\begin{bmatrix}
p \\ s \end{bmatrix} =
\begin{bmatrix} A\_{11} \\ A\_{21}\end{bmatrix}p+ \begin{bmatrix} A\_{12} \\ I \end{bmatrix} s.
\end{align}
If you assume the system is consistent, then $s = -b\_2 - A\_{21}p$. If the system is inconsistent, then you can try to find the solution that least violates it as:
$$(A\_{12}^TA\_{12}+I)s = -A\_{12}^T(b\_1+A\_{11}p) - (b\_2+A\_{21}p).$$
I suppose the system ought to be consistent though.

Edit:

Here's a more general approach as to how you can factorize such problems if you assume $A\_{22}$ is an invertible matrix (it is essentially block Gaussian elimination):

\begin{align}
\begin{bmatrix} b\_1 \\ b\_2\end{bmatrix} &=
\begin{bmatrix}
A\_{11} & A\_{12} \\ A\_{21} & A\_{22}
\end{bmatrix}
\begin{bmatrix}
x\_1\\ x\_2
\end{bmatrix}
\\
\begin{bmatrix}
b\_1 \\ b\_2
\end{bmatrix}
&= \begin{bmatrix}
A\_{11}x\_1 + A\_{12}x\_2 \\
A\_{21}x\_1 + A\_{22}x\_2
\end{bmatrix}
\\
\begin{bmatrix}
b\_1\\
A\_{22}^{-1}(b\_2 - A\_{21}x\_1)
\end{bmatrix}
&=
\begin{bmatrix}
A\_{11}x\_1 + A\_{12}x\_2
\\
x\_2
\end{bmatrix}
\\
\begin{bmatrix}
b\_1 - A\_{12}A\_{22}^{-1}b\_2 \\
A\_{22}^{-1}(b\_2 - A\_{21}x\_1)
\end{bmatrix}
&=
\begin{bmatrix}
(A\_{11}-A\_{12}A\_{22}^{-1}A\_{21})x\_1 \\ x\_2
\end{bmatrix}
\end{align}

In your case $A\_{22} = I$ so the inverse is just $I$. If the Schur complement $[A/A\_{22}]= A\_{11}-A\_{12}A\_{22}^{-1}A\_{21}$ is invertible, then
$$x\_1 = [A/A\_{22}]^{-1}(b\_1 - A\_{12}A\_{22}^{-1}b\_2), \quad x\_2 = b\_2 - A\_{21}x\_1.$$

But it could happen that the Schur complement is not invertible. If $b\_1 - A\_{12}A\_{22}^{-1}b\_2$ is in the range of $[A/A\_{22}]$ you have infinitely many solutions, since if $x\_1^\*$ is a solution, and $w$ is a non-zero vector from the kernel of $[A/A\_{22}]$, then also $x\_1^\* + \alpha w$ is a solution.
Having one such solution $x\_1^\*$ you can compute $x\_2^\* = b\_2 - A\_{21}x\_1^\*$. In the paper they set $x\_1^\* = \frac{p\_1+p\_2}{2}$. I haven't proven that this is necessarily a solution for their matrix though.

The other case is that $b\_1 - A\_{12}A\_{22}^{-1}b\_2$ is
not in the range of $[A/A\_{22}]$. Then there are no solutions. But you can try for the closest thing to a solution in an $L\_2$ sense. Then $$x\_1^+ = [A/A\_{22}]^+(b\_1 - A\_{12}A\_{22}^{-1}b\_2),$$
where $[A/A\_{22}]$ is the Moore-Penrose inverse. You may again set $x\_2 = b\_2 - A\_{21}x\_1^+$.


---

