Questions tagged [linear-system]

For questions about solving linear systems of equations. These typically take the form Ax=b, where A is a matrix , while x and b are vectors.

Filter by
Sorted by
Tagged with
1 vote
2 answers
95 views

Implementing matrix term version of Gauss-seidel

I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
Jared Frazier's user avatar
2 votes
0 answers
76 views

Solving tridiagonal Toeplitz system using SIMD instructions

I need to solve many small Toeplitz systems that fit entirely in cache, meaning the computation is compute bound. Are there vectorizable algorithms for this? I found a few older articles: (https://www....
Pel's user avatar
  • 21
2 votes
1 answer
170 views

Numerically stable way to implement Cramer's rule analog

Problem statement Let $A$ be an $n\times n$ matrix and $b$ an $n$-dimensional vector. For $j\in \{1, \dots, n \}$, let $A_j$ be the matrix where we take $A$ and replace the $j^{\rm th}$ column with $b$...
Joe's user avatar
  • 31
4 votes
2 answers
232 views

Faster than forward substitution?

I have a matrix of the form: $M:=\begin{pmatrix} S_1 & & & \\\ Q_1 & S_2 & & \\\ & ... & ... & \\\ & & Q_n & S_n\end{pmatrix}$ where the blocks ...
Lilla's user avatar
  • 157
3 votes
1 answer
247 views

Is it really necessary to solve a system of linear equations in the Finite Element Method?

When we solve some boundary value problem by Finite Element Method, the appropriate system of linear equations is built, $$Ax=b.$$ Usually we use the solution x just for plugging it into some ...
Fidel Pestrukhine's user avatar
1 vote
0 answers
43 views

FEM Basis for functions of two variables in $\mathbb{R}^2$ (Applied to Linear Full Stokes Equations)

I'm trying to do FEM for a very basic version of the linear full Stokes equations in two dimensions. Say we are working in the grid $[0,1]\times[0,1]$ in the $xy-$plane. To solve an FEM problem for a ...
k12345's user avatar
  • 111
6 votes
1 answer
214 views

Inverse power iteration and solving singular system

The algorithm for the inverse power iteration works as following : \begin{align} &v^{(0)} =\text{ some vector with }\|v^{(0)}\|=1\\ &\text{for }k = 1, 2, \ldots\\ &\qquad\text{Solve } (A - ...
edamondo's user avatar
  • 169
0 votes
0 answers
42 views

Instability due to different lumping dimensions in second-order linear system

I have a problem that consists of a linear hyperbolic differential equation with some boundary and initial conditions which leads after discretization in space using finite elements to the following ...
DanielRch's user avatar
  • 472
0 votes
1 answer
66 views

Solving a linear system whose coefficient matrix is dense but symmetric

For solving a linear system, $Ax = b$. If $A$ is a dense but symmetric $n \times n$ matrix, how much memory is required? $A$ is symmetric, which means only the upper (or lower) triangular part of $n \...
Yonghyun Chung's user avatar
1 vote
0 answers
29 views

Non-Linear Distributed Delayed Kalman Filter

I have a system $\vec{x}_{i + 1} = \vec{x}_i + W_i$ where $W = N(\vec{\mu}, \Sigma)$. For some matrix $H_i$, let $y_i = H_i$ and let $z_i = y_i + R$. Where $R$ is some random variable. We are given $...
JEK's user avatar
  • 23
4 votes
0 answers
142 views

SINDy Vs standard methods for system identification

I have been trying to understand the recently proposed Sparse Identification of Nonlinear Dynamics SINDy. Despite several attempts, I seem to fail to understand the difference between SINDy and the ...
Chenna K's user avatar
  • 875
3 votes
1 answer
226 views

Correctness of direct numerical solution of ill-conditioned linear system

To what extent can you put trust in a numerical solution obtained by direct solver for an ill-conditioned linear system? In other words, how can you test the solution? Dropping it into the system says ...
Fidel Pestrukhine's user avatar
3 votes
0 answers
124 views

Splitting system of equations into linear and nonlinear part and solving separately

I was working on a problem recently (calculating all flows in a network given input and output flows, basically what Hardy-Cross tries to achieve) which can be formulated as a well-determined system ...
nardi's user avatar
  • 131
0 votes
1 answer
68 views

Interpolation and Restriction operators in Multigrid

I saw in several places that interpolation operator ($P$) and restriction operator ($P^T$) are usually transposes of each other (up to multiplication by a constant). As I understood it related to ...
ChaosPredictor's user avatar
0 votes
0 answers
276 views

Solving huge dense square symmetric linear system

I have a linear system of the type $A x = y$ where A is a dense, square, symmetric, positive definite matrix, $x$ a vector of unknown parameters, and $y$ is a vector of observed quantity. I know that ...
pinpon's user avatar
  • 153
1 vote
1 answer
100 views

Elementary question on numerical linear algebra

I’ve been facing a problem of solving linear systems Ax=b arising from discretized PDEs (Stokes equations in particular). Nively, it seems that solving Ax=b should not take much more time than simply ...
P. Trinli's user avatar
4 votes
0 answers
51 views

Pass forward intermediate results during iterative optimization

To investigate a counter-current flow heat exchanger while considering temperature dependent physical properties (such as specific heat $c_\textrm{p,i}$, heat conductivity $\lambda_\textrm{i}$, ...
albert's user avatar
  • 223
3 votes
1 answer
526 views

When do not use preconditioners for sparse linear system of equations?

I'm implementing a solver of Finite Element Method, and to solve the linear system of equations I'm using gmres from MKL of Intel. Exists the option with and without a preconditioning. In what case it ...
yemino's user avatar
  • 515
1 vote
0 answers
83 views

Solution of an underdetermined system stemming from a PDE with Neumann BC

Consider the Poisson's equation in 1D with homogeneous b.c.'s $\mathrm{d} \phi/\mathrm{d} x=0$ with the seven point Laplacian (1 -54 783 -1460 783 -54 1 / 576 on a uniform grid). The resulting system ...
Vladimir F Героям слава's user avatar
0 votes
2 answers
109 views

Simplest solver for linear equation systems

Normally, this boards sees a lot of traffic about the most efficient and most powerful solvers for huge linear equation systems. But this time, I have the opposite problem: I need to implement a ...
Michael's user avatar
  • 1,463
3 votes
1 answer
360 views

Preconditioning vs. regularization

I used to be more of a numerical linear algebra and computational science person, but recently, I've crossed into stats and machine learning. For this discussion, let's focus on matrices that are not ...
anonuser01's user avatar
0 votes
2 answers
2k views

Solve a system of coupled differential equations in Python

I have a system of two coupled differential equations, one is a third-order and the second is second-order. I am looking for a way to solve it in Python. I would be extremely grateful for any advice ...
Wiss's user avatar
  • 33
1 vote
1 answer
152 views

Algebraic multigrid as solver and as preconditioner

My question is around the efficiency of AMG. In which case AMG can perform better,as solver or as a preconditioner(for example a Krylov space method as CG)? Assume the case of elliptic pdes.
spyros's user avatar
  • 481
0 votes
0 answers
157 views

Solving a linear system with block-banded matrix

It is required to solve a linear system $Ax=b$, where the matrix $A$ is symmetric, all the variables and coefficients are real. The structure of $A$ is \begin{equation} A = \begin{pmatrix} A_{11} &...
DanielRch's user avatar
  • 472
3 votes
0 answers
82 views

Kronecker-factored least-squares?

Suppose $a_i,b_i$ are $d\times 1$ matrices, $y_i$ is scalar, and I need to find least-squares solution $w$ of the following system of $n$ equations: $$y_i=(a_i^T\otimes b_i^T)w$$ Is there a ...
Yaroslav Bulatov's user avatar
2 votes
1 answer
376 views

Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular

I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
krishnab's user avatar
  • 287
1 vote
1 answer
456 views

Solution of Coupled Differential equation for a 2d linear flow using RK4 method in python 3

I want to study the dynamics of a 2d linear flow, whose dynamical equation is- $\begin{pmatrix} \dot{x_1}\\ \dot{x_2}\\ \end{pmatrix}=\begin{pmatrix} 1 & 1\\ 4 & -2\\ \end{pmatrix}\begin{...
Anirban Majumdar's user avatar
4 votes
2 answers
418 views

1D FEM for nonlinear diffusion coefficient

I want to solve with linear finite elements the equation $$\partial_t u = \partial_{x}(a(u)\partial_xu)$$ in the domain $t \in [0,1]$ and $x \in [-L,L]$. Here $a(u)$ is just a function of $u$. ...
Vefhug's user avatar
  • 309
0 votes
1 answer
155 views

Is it possible to predict solution oscillation before solving the system by looking at coefficient matrix?

Question When it is about solving a system of equations, is it possible to predict that whether high-frequency noise (e.g. checker-boarding) is likely to appear in the converged solution by looking at ...
Naghi's user avatar
  • 235
2 votes
2 answers
984 views

Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB

Let $n = 10^6.$ Let $A \in \mathbb{R}^{n\times n} $ be the lower triangular matrix having 1's on and below the main diagonal. We want to solve the following linear system: $$ (A + uv^T)x = b$$ by the ...
user avatar
5 votes
1 answer
198 views

Accurately Computing a Positive Vector in the Nullspace of a Matrix

I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer. The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
cyfirx's user avatar
  • 53
2 votes
1 answer
138 views

Solving an m x m symmetric linear system involving a matrix multiplication versus an (n+m) x (n+m) system

Suppose that $R$ and $D$ are an $n \times m$ and $m \times m$ matrices. Assume that $m \ll n$ and that $D$ is positive definite. We would like to solve the system $(R^T R + D) x = R^T b$. This ...
passerby51's user avatar
4 votes
1 answer
456 views

Without positive definiteness, does an iterative solver work?

Question Does lacking positive definiteness of the matrix of coefficients in a system of equations, make using iterative solvers impractical? Description Using the finite volume method, I have ...
Naghi's user avatar
  • 235
1 vote
2 answers
451 views

Why OpenFOAM uses its own data structures and linear solvers?

I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++? Another ...
IamNotaMathematician's user avatar
3 votes
3 answers
537 views

Using matrix exponential to solve linear system

Consider the system of linear equations: $$ Ax=b \tag{1} \label{eq1} $$ where $A\in\mathbb F^{n\times n}$, diagonalizable dense matrix, over the field $\mathbb F$ of real or complex numbers, $x\...
Anton Menshov's user avatar
  • 8,602
1 vote
0 answers
123 views

Linearize non-linear PDE with BCs to hyperbolic problem: How does linearization affect BCs?

I am working with the Shallow Water equations that is a system of non-linear PDEs that simulate water waves propagation on some domain, in my cases the $x$-axis. I have here a GIF showing the results (...
SimpleProgrammer 's user avatar
1 vote
1 answer
83 views

How to properly compute weights for Weighted Least Squares (WLS)?

I want to apply the weighted least squares method in order to identify parameters of a dynamic process. The process is described by a second order differential equation of the form: $$ \ddot{y}+a_1\...
Teo Protoulis's user avatar
5 votes
0 answers
130 views

Levinson Recursion for Non Square Toeplitz Matrices

Given a rectangular Toeplitz Matrix $ H $, how could one solve: $$ y = H x $$ For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $: $$ H = \begin{bmatrix} {h}_{1} & 0 & ...
Royi's user avatar
  • 332
3 votes
1 answer
2k views

How to implement flexible gmres in matlab?

About the flexible GMRES (fgmres), we know that it is a variant of right preconditioned gmres. And the robust command gmres in matlab as follows: ...
Happy's user avatar
  • 961
1 vote
0 answers
121 views

How to compute the computational cost and storage of the Full Orthogonalization Method?

About the analysis of Full Orthogonalization Method (FOM) in Prof. Saad's book, wrote as follows: Algorithm 6.4 (FOM): \begin{array}{l} r_0=b-Ax_0,\beta=\|r_0\|_2,v_1 = r_0/\beta\\ Define \quad H_m ...
Happy's user avatar
  • 961
3 votes
0 answers
218 views

How to reproduce the numerical examples in Prof. Saad's Book about Krylov subspace methods?

After reading Prof. Saad' Book, "Iterative methods for Sparse Linear Systems, 2nd version", I want to do the numerical examples about the Krylov subspace methods not only to reproduce the results in ...
Happy's user avatar
  • 961
2 votes
2 answers
473 views

How to understand the choice of Krylov subspace orthonormal basis?

This semester, I study the Krylov subspace iterative methods (about Ax=b) using the book H. A. Van der Vorst. Iterative Krylov Methods for Large Linear Systems, volume 13. Cambridge University Press, ...
Happy's user avatar
  • 961
4 votes
3 answers
224 views

Solving for a vector in a linear system that is both left and right multiplied

I have a linear system where I am given 2 matrices, $A$ and $B$, and 2 vectors, $v$ and $c$, and I need to solve for the vector $x$. $A$ is $n\times n$, $B$ is $n \times n \times n$, and the vectors $...
EMP's user avatar
  • 2,069
3 votes
1 answer
79 views

Does the k-th approximate solution of a stationary iteration belong to the k-th Krylov subspace?

For an stationary iteration method solving $Ax=b$ as follows: $$ Mx_k = Nx_{k-1}+b, $$ I have known that when $M = I$, i.e., the Richardson iteration, the k-th solution $x_k = x_{k-1}+r_{k-1}$ is in ...
Happy's user avatar
  • 961
2 votes
1 answer
111 views

What is the standard, extrapolation, and modified version of Richardson iteration method?

I have been studying the iterative methods recently. For classical iterative methods solving $Ax=b$, I have seen that the most simplest iteration method is the so-called "Richardson iteration". But I ...
Happy's user avatar
  • 961
2 votes
1 answer
560 views

Why Krylov subspace iterative methods are faster than classical iteration?

This semester, I have been studying the most popular iterative methods, i.e., Krylov subspace iteration methods. For a large sparse system linear $$ Ax=b, $$ where $A$ is nonsingular, I know that ...
Happy's user avatar
  • 961
1 vote
0 answers
43 views

What kind of problem or matrices are suitable for multigrid method?

For Poisson or Convection-diffusion equation as follows: $$ -\Delta u=f,\qquad u|_\Omega = g. $$ or $$ -\Delta u +\vec{w}.\nabla u=f,\qquad u|_\Omega = g. $$ using FDM or FEM discretization, we can ...
Happy's user avatar
  • 961
1 vote
1 answer
91 views

Why do not we choose the error solution norm as an iterative method's criterion?

For solving linear system $$ Ax=b, $$ using iterative mehods, we often use the terminate criterion as follows: $$ \frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps. $$where $x_0$ is the ...
Happy's user avatar
  • 961
2 votes
3 answers
307 views

Is there any other sparse matrix data in matlab built-in file?

I want to do some numerical examples solving large sparse linear system Ax=b. And I want to use some data from Maltab itself because this experiments are easily ...
Happy's user avatar
  • 961
3 votes
1 answer
500 views

What is the **contraction factor and convergence factor** of a iteration method?

For any iteration method from A=M-N, e.g., $$ Mx_{k+1}=Nx_{k}+b,\quad k=0,1,... $$ we know that it converges iff $\rho(M^{-1}N)<1$. And when it converges, there exists a concept called asymtotic ...
Happy's user avatar
  • 961