Daniel Shapero
  • Member for 9 years, 1 month
  • Last seen this week
Are direct solvers affected by the condition number of a matrix?
Accepted answer
27 votes

Yes, the condition number always matters in floating-point arithmetic, whether you choose to solve your system with an iterative or direct method. The relative accuracy of an approximate solution to $...

View answer
Why are log and exp considered 'expensive' computations in ML?
Accepted answer
19 votes

To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Agner Fog. For example, on the Intel Ivy Bridge processors: FADD / FSUB (floating ...

View answer
full rank update to cholesky decomposition
Accepted answer
15 votes

In general, there is no shortcut other than completely re-factoring the matrix. There have been a few similar questions on this SE that cover the topic in more depth than I can: Can diagonal plus ...

View answer
Finite elements $W^{1,\infty}$ error estimates
Accepted answer
14 votes

Chapter 8 of Brenner and Scott's Mathematical Theory of Finite Element Methods is devoted to this subject. In particular, theorem 8.1.11 and the corollary give you that $ \|u - u_h\|_{W^1_\infty} \le ...

View answer
What's the difference between conjugate gradient method and biconjugate gradient method
Accepted answer
14 votes

The conjugate gradient method is the provably fastest iterative solver, but only for symmetric, positive-definite systems. What would be awfully convenient is if there was an iterative method with ...

View answer
Why does SciPy eigsh() produce erroneous eigenvalues in case of harmonic oscillator?
Accepted answer
13 votes

The degeneracy of some eigenvalues looks to me like the hallmark of the breakdown of the Lanczos algorithm. The Lanczos algorithm is one of the more commonly used methods to approximate the ...

View answer
Finite-difference software for solving custom equations
12 votes

I'm going to assume since you mention electrodynamics that you're interested in PDEs. You've already mentioned FEniCS in your comment. FEniCS offers a domain-specific language (DSL) called UFL. This ...

View answer
Galerkin method: Test functions vs. Basis functions
Accepted answer
12 votes

Suppose that the solution $u$ of the PDE lives in some function space $X$. We'll write the PDE as a bilinear form $A(u, v) = f(v)$ for all $v$ in $X$, where $f$ is some element of the dual space $X^*...

View answer
Genetic algorithm vs conjugate gradient method
12 votes

The conjugate gradient method is good for finding the minimum of a strictly convex functional. This is typical when you reformulate a nonlinear elliptic PDE as an optimization problem. If you want to ...

View answer
Nonlinear wave equation - Finite element or finite difference
Accepted answer
11 votes

If it's shock-capturing that you're interested in, I would suggest you use the finite volume method instead of the finite element method. When applied naively, FEM is actually notoriously bad at ...

View answer
How do I find the minimum-area ellipse that encloses a set of points?
10 votes

With your formulation of the constraints, you can only produce ellipses where the semi-major and semi-minor axes are aligned with the coordinate axes, but it's clear from the figure that you attached ...

View answer
Writing a parallel version of an algorithm. Only which someparts are worth distributing
Accepted answer
10 votes

If the operation is as trivial as you say, and each node has all the information necessary to carry out the operation, then the communication will be substantially more expensive than recomputing ...

View answer
Fourier Transform of function in Spherical Harmonics
Accepted answer
10 votes

You may find the expansion of a plane wave in spherical waves to be helpful here: $$ e^{i\mathbf{k}\cdot\mathbf{x}} = 4\pi\sum_{l=0}^\infty\sum_{m=-l}^l i^lj_l(kr)Y_{lm}(\theta,\phi)Y_{lm}^*(\...

View answer
Is Crank-Nicolson a stable discretization scheme for Reaction-Diffusion-Advection (convection) equation?
10 votes

Generally speaking, you'll want to use an implicit method for parabolic equations (the diffusion part) -- explicit schemes for parabolic PDE need to have a very short timestep to be stable. Conversely,...

View answer
Who uses finite elements with higher continuity?
9 votes

This paper by Kirby and Mitchell describes the implementation of $C^1$ elements in the Firedrake package*. One of the main use cases is biharmonic problems, which show up in the elastic deformation of ...

View answer
Interpolate the orbital coordinates of an object using coordinates and velocities vector
8 votes

That depends on how well you know the coordinates and velocities. If you have exact values, you can get a reasonable answer using Hermite interpolation. This will give you a degree-3 polynomial in ...

View answer
How to determine if a point is outside or inside a curve
Accepted answer
8 votes

There's a simple test to see if a point $(x, y)$ is enclosed within a curve. Draw a ray from $(x, y)$ to infinity, and count how many times it crosses the curve; if the count is odd, then $(x, y)$ is ...

View answer
Recommendations for symmetric preconditioner
8 votes

Often $M^{-1}A$ is not symmetric, even if $M$ and $A$ are. There are two common approaches to dealing with this: Find a Cholesky factorization of $M$ into $LL^\top$, and instead solve for $L^{-1}AL^{-...

View answer
fastest linear system solve for small square matrices (10x10)
7 votes

Using an Eigen matrix type where the number of rows and columns is encoded into the type at compile time gives you an edge over LAPACK, where the matrix size is known only at runtime. This extra ...

View answer
Inverse advection-diffusion problem, solving for a drift coefficient with experimental data?
Accepted answer
7 votes

There is another approach called the adjoint method, which is commonly used in inverse problems for PDE and which is quite easy to generalize to other problems. This is going to be long. Your ...

View answer
Solving Lx = b for big sparse Laplacian matrices
Accepted answer
7 votes

Which one was faster when you tried using Eigen? You may also consider Trilinos if you're using C++. By "generic Laplacian matrix", do you mean a finite difference / finite element discretization of ...

View answer
What is the fastest way to compute all eigenvalues of a very big and sparse adjacency matrix in python?
Accepted answer
7 votes

FILTLAN is a C++ library for computing interior eigenvalues of sparse symmetric matrices. The fact that there is a whole package devoted to just this should tell you that it's a pretty hard problem. ...

View answer
Rearrange an ordinary matrix to block diagonal form
Accepted answer
7 votes

Is the matrix sparse or dense? Is it symmetric? I'm assuming by "rearrange" you mean permute the entries, rather than apply some more general similarity transformation to the matrix. In that case, ...

View answer
Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates
Accepted answer
6 votes

If the only non-zero entries of $A_{ij}$ have $j$ in $\{i - 1, i, i + 1\}$, then $A$ is a banded matrix with bandwidth 1. More generally, you can talk about matrices of bandwidth $k$ where $k$ is any ...

View answer
How to calculate $\arg(z_1z_2\cdots z_n)$ to minimize results error?
Accepted answer
6 votes

As Brian Borchers pointed out, the question only makes sense up to factors of $2\pi$. I'll assume that you want an answer in $[0, 2\pi)$ then. If there are really big contrasts in the magnitudes $|...

View answer
Do I need to impose boundary conditions in the Jacobian matrix?
6 votes

There are multiple ways of implementing Dirichlet boundary conditions when using the finite element method. For each unknown $i$ of the system belonging to the Dirichlet boundary, you can zero out ...

View answer
nonoverlapping domain decomposition
Accepted answer
6 votes

Short answer: yes, you have to use something different, e.g. a Neumann-Neumann method. A good reference is Widlund's book. Non-overlapping methods are based on the principle that, if $u$ solves the ...

View answer
fortran code-algorithm for qr decomposition of non-square matrix
6 votes

Trefethen and Bau's book Numerical Linear Algebra has the Householder QR algorithm in chapter 10, and it's written considering general rectangular matrices. It's also in Matrix Computations by Golub ...

View answer
What algorithms are known for computing exact eigenvalues for rational matrices?
6 votes

The characteristic polynomial of a matrix $M$ can be written as $\chi_M(z) = z^n + \textrm{trace(M)}z^{n-1}+\ldots + \det(M)$. Since you know ahead of time that all the entries of $M$ are rational, ...

View answer
Library that performs sparse matrix-vector and matrix-transpose-vector multiplication
6 votes

Usually you would do one of two things: Compute $z = Ax$, then $y = y+Az$; If you anticipate needing to do this operation many times, you might compute the matrix $B = AA'$ and then evaluate $y = y+...

View answer
1
2 3 4 5