8
votes
Compute $x = B^{-1}(2A+I)(C^{-1}+A)b$ without calculating matrix inverses
As was mentioned in the comment, calculating $x=M^{-1}y$ is equivalent to solving $Mx=y$. Here is the full solution:
First, you can reformulate the equation to:
$Bx=(2A+I)(C^{-1}+A)b$, and by ...
- 402
8
votes
Accepted
Solving $AX+X^TB=C$?
It is called a T-Sylvester equation, or *-Sylvester equation in the complex case. Solvability conditions and a pseudocode algorithm based on the Schur form are in https://doi.org/10.13001/1081-3810....
- 12.6k
5
votes
Recurrence relation for matrices
This is an instance of the Riccati equation, which can be solved using the Matrix Sign function. Relevant section from Higham's "Functions of Matrices" book:
- 2,799
5
votes
Accepted
Maximize a function of an orthogonal matrix
There are specialized methods for the minimization of a differentiable function $f(X)$ subject to the orthogonality constraint $X^{T}X=I$. See for example:
Lai, Rongjie, and Stanley Osher. “A ...
- 19k
5
votes
The fast, and The Backward-Stable (left) $3\times 3$ matrix inverse
I will try to give my thought on the first question regarding fast $3\times 3$ inverse. Consider
$$
A=\left[
\begin{array}{ccc}
a & d & g\\
b & e & h\\
c & f & i
\end{array}\...
- 8,742
5
votes
Confusion about matrix differentiation in a nonlinear matrix equation
If a matrix is differentiated with respect to itself, the result should be a fourth order tensor. The easist way to see this is to work with components.
$$
\frac{ \partial K_{ij}}{\partial {K_{kl}}} = ...
- 852
4
votes
Accepted
Mass Matrix and how to handle it (ODEs) - References
Ignoring Newton's method here is the wrong approach! The fact that you're using Newton's method is what makes this cheap to add, and is what makes singular mass matrices possible. Essentially look at ...
- 12.5k
4
votes
Accepted
Solving linear system with matrix multiplication
The beauty of iterative methods is that all they require you to do is matrix-vector multiplications. In your case, the product of your matrix $A$ with a vector $y$ can be written as $z=Ay = (B^TCB)y= ...
- 56.8k
4
votes
How can I express the solution to a discrete Lyapunov equation as an eigenvalue problem?
For completeness, I'm including a full derivation for the solution of the discrete Lyapunov equation that is adapted from @FedericoPoloni's paper (specifically section 4.1). For the derivation for the ...
- 175
4
votes
Accepted
Solving underdetermined Lyapunov equation?
Since $A$ is symmetric, it has an eigendecomposition $A = QDQ^*$ with $Q$ orthogonal. Then
$$
M = A \otimes I + I\otimes A = (Q\otimes Q)(D\otimes I + I \otimes D)(Q\otimes Q)^*
$$
is an ...
- 12.6k
4
votes
Solving for $X$ in $\sum_{a,b} b a^T b^T X a = Y$
Conjugate gradient (in a matrix-less implementation) might be a good idea to try. You have a $d^2\times d^2$ symmetric positive semidefinite matrix for which you can compute the action of the matrix-...
- 12.6k
3
votes
Maximize a function of an orthogonal matrix
A simple way to introduce orthogonality constraints is to parametrize all orthogonal matrices using, either, the Cayley transform, $Q=(I-A)(I+A)^{-1}$, or the matrix exponential, $Q = \exp(A)$. In ...
- 1,091
3
votes
Accepted
Solution $X$ for $X(X^TX)^{-1}=X(Y^TY)^{-1}$
Notice that $X(X^T X)^{-1}$ is the Moore-Penrose inverse of $X^T$. Using properties of pseudo-inverse we get
$(Y^TY)(X^T X)^\dagger = I$
For instance $X=Y$ or $X=\text{Cholesky}(Y^T Y)$
- 2,799
3
votes
Solution to Sylvester-like equation
EDIT: this answer is essentially useless after the question was updated. If the coefficients $A,B$ are symmetric, these approaches reduce to the simpler closed formula with the eigenvalue ...
- 12.6k
3
votes
Accepted
Solution to Sylvester-like equation
Working with a more standard form of a Stein equation, sometimes called (generalized?) Discrete Lyapunov Equation
$$AXB - X = C$$
Rewrite it in standard linear equation form, use least squares solver,...
- 2,799
3
votes
Accepted
Matrix regularisation for ill-conditioned problems
matrix regularisation can improve the stability of LU or Cholesky decomposition of ill conditioned problems.
Not really, at least in the way the word "stability" is typically used in the ...
- 12.6k
3
votes
Accepted
Matrix derivative
Per the very helpful wikipedia page "derivative of the exponential map", based around the "Baker-Campbell-Hausdorff formula", the relevant formula for a directional derivative is
$\...
- 6,159
3
votes
Matrix derivative
Observing that both the trace and the multiplication with a matrix $A$ are linear operations, it is easy to apply the chain rule. For this, first see that
$$
\frac{\partial}{\partial X_{ij}} [\text{...
- 56.8k
3
votes
Accepted
Recurrence relation for matrices
Another different way to obtain an equivalent formula: let $Y = A^{1/2}XA^{1/2}$. Then, multiplying your equation from both sides by $A^{1/2}$, we have $Y^2+Y = A^{1/2}BA^{1/2} = C$.
The matrix $C$ ...
- 12.6k
3
votes
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I encountered a similar problem in the past and I could find no simple solution either. One of the terms is a Kronecker product, another is a rank-1 modification, but the rest makes the problem more ...
- 12.6k
3
votes
Invert a matrix only on a subset of variables / Compute the "equivalent circuit"
The procedure you need to get the "reduced" equations is often referred to as "static condensation" in the FEM literature. You can
partition your FE equations as follows:
$$
\left[\begin{array}{cc}
...
- 6,339
3
votes
Solve linear system for only part of the solution vector
The only way that I'm aware of to take advantage of only needing a partial solution is in the triangular solves. But those are usually a small part of the total time in dense LU (unless you have many ...
- 988
2
votes
Accepted
Least Squares with Dense-Block Diagonal Structure
If $N$ is on the order of 100,000 and $m$ is on the order of $100$, Then
$J$ requires about 80 gigabytes to store in double precision and $V$ requires a trivial amount of storage. The product $M=JV$ ...
- 19k
2
votes
Eigenvalue-like problem with coupled ODEs
Assume the equations are discretized on the $\tau$ grid, and introduce several column-vectors, using the notation where the superscript stands for the grid point index i $\in$ [1,...,n].
$\vec{\tau}=\...
- 2,655
2
votes
Matrix derivative
$
\def\o{{\tt1}}
\def\LR#1{\left(#1\right)}
\def\op#1{\operatorname{#1}}
\def\vc#1{\op{vec}\LR{#1}}
\def\rs#1{\op{Unvec}\LR{#1}}
\def\Diag#1{\op{Diag}\LR{#1}}
\def\diag#1{\op{diag}\LR{#1}}
\def\trace#...
- 654
2
votes
Accepted
How can I express the solution to a discrete Lyapunov equation as an eigenvalue problem?
You can do it with symplectic matrix pencils instead of Hamiltonian matrices, even in the more general case of discrete-time algebraic Riccati equations.
$$
\begin{bmatrix}
A & 0\\
-Q & I
\end{...
- 12.6k
Only top scored, non community-wiki answers of a minimum length are eligible