Computational Science Stack Exchange
Computational Science Stack Exchange

Most Popular

more tags
1500 questions
9
votes
3 answers

Computing the characteristic polynomial of real sparse matrix

Given a generic sparse matrix $A \in \mathbb{R}^{n\times n}$ with m << n (correction: $m \ll n^2$) non-zero elements (typically $m \in {\cal O}(n)$). $A$ is generic in the sense that it has no specific properties (e.g. positive definiteness), and no…
user182
9
votes
1 answer

How does LAPACK solve tridiagonal systems and why?

In my project I have to solve a couple of tridiagonal matrices at every time step, so it is crucial to have a good solver for those. I did my own implementation, just the classical way to do it described on Wikipedia. I then tried using Lapack…
tiam
  • 864
  • 7
  • 18
9
votes
4 answers

Condition number of A'A and AA' formulations

It's shown (Yousef Saad, Iterative methods for sparse linear systems, p. 260) that $cond(A'A) \approx cond(A)^2$ Is this true for $AA'$ as well? In case $A$ is $N\times M$ with $N \ll M$, I observe that $cond(A'A) \gg cond(AA')$ Does that mean…
Alexander
  • 1,111
  • 1
  • 8
  • 15
9
votes
1 answer

Numerically stable algorithms for computing remainder of polynomials

Let $f, g \in \mathbb{R}[x]$ and $\deg f > \deg g$. I am looking for asymptotically fast and numerically stable algorithms for computing $f \bmod g$. In the applications intended, both $f, g$ are dense polynomials with double precision…
user182
9
votes
3 answers

Standard format for finite element meshes

Does there exist a standard format for finite element meshes which is widely used in the industry? Thanks!
Benjamin
  • 265
  • 1
  • 4
9
votes
4 answers

Fast explicit solution for $\mathbf{A}\mathbf{x} = \mathbf{b}$, $ \mathbf{b} \in \mathbf{R}^3$, low condition number

I am looking for a fast (dare I say optimal?) explicit solution the 3x3 linear real problem, $\mathbf{A}\mathbf{x} = \mathbf{b}$, $\mathbf{A} \in \mathbf{R}^{3 \times 3}, \mathbf{b} \in \mathbf{R}^{3}$. Matrix $\mathbf{A}$ is general, but close to…
Damien
  • 802
  • 4
  • 10
9
votes
3 answers

What are the differences between CFD simulations and realistic ocean/atmosphere model simulations?

The field of computational fluid dynamics (CFD) is dedicated to solving the Navier-Stokes equations (or some simplification of them). A subset of CFD, ocean and atmospheric models numerically solve the same equations for realistic applications. What…
arkaia
  • 201
  • 1
  • 10
9
votes
1 answer

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\mathbb{R}^{n\times m}$, I would like to solve the…
Justin Solomon
  • 1,341
  • 7
  • 24
9
votes
2 answers

Boundary conditions Chebyshev differentiation

I was wondering if anyone has any experience dealing with boundaries when implementing chebyshev differentiation. I am currently trying to implement a no slip boundary condition to solve the incompressible Navier Stokes equations in 3D, in order to…
weddle_32
  • 111
  • 3
9
votes
2 answers

Solving Lx = b for big sparse Laplacian matrices

What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, its first eigenvalue being null in most cases).…
teodron
  • 193
  • 6
9
votes
4 answers

How do I know which low-discrepancy sequence to use?

Whenever one uses a quasi-Monte Carlo method for cubature or optimization, it seems that there's a wide variety of low-discrepancy sequences to choose from, associated with the names of van der Corput, Halton, Hammersley, Faure, Niederreiter,…
J. M.
  • 3,155
  • 28
  • 37
9
votes
2 answers

Sparse smallest eigenvalue problem on a linear subspace?

I am interested in methods for solving the optimization problem $$ \begin{array}{rl} \arg\min_x & x^T A x \\ \mathrm{s.t.} & x^T x = 1 \\ & Bx = 0 \end{array} $$ where $A$ is symmetric and full rank with well-separated eigenvalues, and $B$ has a…
BovineButterworth
  • 91
  • 2
9
votes
1 answer

Given values on a mesh, what algorithm can I use to construct efficiently level set contours?

I have a mesh, faces $F$, edges $E$, and vertices $V$, and I have a list of predefined level set contours. What algorithm can I use to construct contours in the most efficient manner? A plot of the contour is shown above. Lines with the same color…
Graviton
  • 488
  • 5
  • 16
9
votes
3 answers

Accurate Polynomial Evaluation in Floating Point

What are the most accurate algorithms for evaluating a polynomial using floating point arithmetic? The internet seems to suggest that Horner's method is commonly used. In particular I have a cubic polynomial of the form f(x) = a x^3 + b x^2 + c x +…
Christopher Johnson
  • 471
  • 3
  • 9
9
votes
1 answer

Algorithm to calculate the exponential of an Hessenberg matrix

I am interested in computing the solution of a lage system of ODEs using a krylov method as in [1]. Such method involve functions related to the exponential (the so-called $\varphi$-functions). It essentially consists of computing the action of the…
Christine Darcoux
  • 427
  • 2
  • 10
1 2 3
…
99 100