Numerical algorithms for problems in analysis and algebra, scientific computation

**7**

votes

**2**answers

320 views

### How to solve a system of linear equations without storing the matrix?

I have a procedurally defined Hermitian matrix $M$, i.e. I can get any matrix element by calling a black box function (e.g. a library function), and a vector $Y$. And I have to solve a system of ...

**4**

votes

**4**answers

840 views

### When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...

**1**

vote

**0**answers

99 views

### Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...

**0**

votes

**0**answers

26 views

### Problem with the convergence of a Nystrom algorithm

I programmed a Nystrom Algorithm specifically for my problem:
This is the exact equation i want to solve:
$y''=(w^2-e*cos(t))*sin(t)-b*y'$
And this is my algorithm
...

**1**

vote

**1**answer

150 views

### An upper bound on a simple sum

Hi,
I am trying to put a bound on a sum. Given $\omega=\exp(2\pi i/3)$ and $n$ positive real numbers
$ 0=\tau_0 < \tau_1 < \tau_2 < ...\tau_{n-1}< \tau_n=1 $
such that
...

**4**

votes

**1**answer

320 views

### Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
...

**2**

votes

**0**answers

138 views

### Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...

**0**

votes

**0**answers

139 views

### How to interpolate in 3-D non-euclidean space?

Assume, one has a 3-D non-euclidean space of points $p_i = \left(x_i, y_i, z_i\right) \in \mathcal{R}^2 \times \mathcal{R}_{> 0}$ with the following "distance" function $d\left(p_1, p_2\right) = ...

**1**

vote

**1**answer

284 views

### Books on Numerical Methods for Partial Differential Equations

Any good references for undergraduates?

**4**

votes

**1**answer

498 views

### Solution of Helmholtz-Equation where Phase is restricted by additional PDE

Hello!
Let's say I have
$(\partial_x^2 + \partial_y^2 + a)f(x,y)=0$
with $f(x,y) \in \mathbb{C}$, ($\lim_{x,y \to \infty} f(x,y)=0$).
Now separate the Amplitude and Phase of the solution:
...

**6**

votes

**1**answer

150 views

### Algorithm for numerically approximating the Prokhorov metric?

Question: What is known about algorithms for numerically computing/approximating the Prokhorov distance between two measures?
Recall that the Prokhorov distance metrizes the topology of weak(-*) ...

**8**

votes

**7**answers

2k views

### Any good books on numerical methods for ordinary differential equations?

I need to find some masters-level exercises about numerical methods for solving ODEs. Are there any good references?

**5**

votes

**1**answer

1k views

### Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...

**1**

vote

**2**answers

342 views

### Condition Number related to Root finding problems

Suppose we want to find the root of the equation $f(x)=\phi(x) - d = 0$, where d is a real constant and $f$ is continuously differentiable function.
The problem is well posed if the inverse ...

**1**

vote

**2**answers

283 views

### Delauney triangulation in high (>20) dimensions

Hi all,
I know that its very hard to find the Delauney triangulation of high dimensional spaces, especially if there are several thousand points that need to be triangulated.
So I was wondering . . ...

**1**

vote

**3**answers

323 views

### What software one needs to solve a big linear system on a small computer?

A time ago I was intrigued by the following remark:
"... one ends up with a (non-sparse) system of equations in
about 10000 real variables. One important practical point is
that solving such systems ...

**4**

votes

**1**answer

221 views

### Most orthogonal lattice basis

Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...

**0**

votes

**1**answer

259 views

### Solving system of nonlinear equations

Dear all,
Can anyone tell me all the algorithms that are available for finding all solutions of a system of nonlinear equations?
I am particularly interested in solving problems of the form:
...

**0**

votes

**1**answer

440 views

### Global Error Analysis of Euler's Method

I know that the local error at each step of Euler's method is O(t^2), where t is the time step. And since there are (b-a)/t steps, the order of the global error is O(t).
However, I saw a derivation ...

**2**

votes

**0**answers

171 views

### fast multipole method and geometric algebra

Hello,
I just learned about fast multipole method(FMM) from this article http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf and I really liked the use of complex numbers in 2d. But I didn't ...

**6**

votes

**4**answers

649 views

### Applications of Hodge-de Rham Laplacian on p-forms ($p\neq 0,n$) in physics or engineering

The Hodge-de Rham Laplacian $L=(d+d^*)^2$, where $d$ is the boundary operator of the de Rham complex, is well-known in the math community. Recently, I tried very hard to search for examples of its use ...

**2**

votes

**1**answer

83 views

### Is is preferable to use a difference formula of higher order of accuracy for spatial derivatives to solve this IVP problem ?

I want to numerically integrate the equation $\partial_t u= a(t) \partial_xu+b\partial_{xxx}u+c$ to get $u(t)$. Is is preferable to use a difference formula of higher order of accuracy for spatial ...

**0**

votes

**0**answers

55 views

### Ways to decompose a torus for finite element method so that each cell contains a complete revolution of the major radius

I've got a finite element problem involving paths around the interior of a torus. For this particular problem I think I could make things more computationally efficient if each cell in the mesh made ...

**5**

votes

**1**answer

417 views

### Numerical Methods for ODEs - History

Wikipedia presents a timeline of important developments in Numerical Methods for ODEs, namely:
...

**-5**

votes

**2**answers

666 views

### why do we need algorithms, and why is non-convex optimization difficult? [closed]

A simple question, but (I'm quite sure) not a superficial one: is the basic distinction between algorithms and much of the rest of math that algorithms try to tackle problems for which we lack global ...

**1**

vote

**2**answers

326 views

### Gauss Legendre Method for Implicit Integration

Methods that are usually adopted for time integration in transport phenomena problems are either:
Euler (explicit, first-order accurate)
$\frac{dY}{dt}=f(t,Y)$
$Y^{n+1}=Y^n+\Delta t f(t,Y^n)$
...

**1**

vote

**1**answer

380 views

### Series acceleration for more complicated types of oscillating series

Question: It is well known that the greatest integer function has a Fourier series representation. Since the greatest integer function itself is not periodic, the representation is derived from the ...

**1**

vote

**0**answers

65 views

### Is there a Krylov subspace method for solving D+epsilon*S where D is diagonal, epsilon small and S skew-symmetric

I'm working on a problem that gives a matrix system of the form D + epsilon*S, where S is a skew-symmetric matrix. I'm interested in finding if any work has been done to develop a conjugate gradient ...

**2**

votes

**1**answer

370 views

### Valid use of Laplace's method?

I am trying to say something about the asymptotics of
$$\int_{\mathbb{R}} e^{cx - x^{4/3}}dx$$
as $c \to +\infty$, and need a sanity check. As I understand it, Laplace's method is to write
$$q(x) = ...

**0**

votes

**1**answer

234 views

### Discrete Sobolev space of $R^n$ valued maps

Can some one tell me the reference or any idea how to take the Discrete Sobolev space work defined for a scalar valued map to the space of maps which are vector valued.Let's say
$f:\Omega ...

**1**

vote

**2**answers

225 views

### Approximation by polynom 1) with respect to supremum-norm 2) I need F_{approx} > F_{exact}

Given a function F, how to find polynom which is best/good approximate with respect supreremum-norm, i.e. minimize over P_{approx} sup|F-P_{approx}| ?
I am intersted in polynoms in two variables of ...

**1**

vote

**0**answers

79 views

### numerical methods for discontinuous ODEs

Greetings,
what are state of art methods for numerical solution of ODEs with discontinuous right side?
I'm mostly interested piecewise-smooth right side functions, e.g. sign.

**4**

votes

**1**answer

161 views

### Estimating the volume of a semialgebraic set from above

Suppose $S$ is a subset of $\mathbb{R}^n$ of finite volume defined by a system of finitely many polynomial inequalities with integer coefficients. Can anyone describe an algorithm that, given such a ...

**2**

votes

**1**answer

225 views

### Numerical integration for functions of symmetric matrices

This is mostly a reference request. I have integrals of the type
\begin{equation}
\int_C f(A) (dA)
\end{equation}
where $f$ is a real-valued function of a positive-(semi)definite matrix ...

**2**

votes

**1**answer

202 views

### Best constant in a convex polynomial inequality.

Let $\phi(x)$ be a convex polynomial of degree $m$ at least two. Note that for $x,q \in \mathbb{R}$
$$\phi(x) + \phi(q) - 2\phi(\frac{x+q}{2}) =
...

**6**

votes

**4**answers

573 views

### solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...

**0**

votes

**0**answers

123 views

### Can we separate Toeplitz matrices for negative and positive eigenvalues?

Consider a Toeplitz matrix T which has both positive and negative eigenvalues. Can we prove that there exist two Toeplitz matrix T1 and T2 such that T1+T2=T and T1 has only one positive Eigenvalues ...

**2**

votes

**0**answers

289 views

### How to apply Lagrange Multipliers to BCs of Time Dependent problems using finite elements?

I am trying to implement a finite element scheme using the method of lines (finite difference in time and finite element in space) and enforcing boundary conditions using Lagrange Multipliers. This ...

**7**

votes

**2**answers

1k views

### Finding the smallest eigenvalues of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $M$. $M$ is a Laplacian matrix, and it has the following structure: ...

**8**

votes

**4**answers

658 views

### What is the theoretical interest of finding closed-form sols. of infinite series?

Hi,
I was reading this when I came across Gourevitch's conjecture.
My understanding is that solutions to these series are of practical interest. If one encounters such a series, being able to solve ...

**1**

vote

**2**answers

192 views

### Triangular grid with 4 edges per vertex

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?

**1**

vote

**1**answer

178 views

### Distributions induced by (weighted) random walks on the integer lattice

Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ ...

**7**

votes

**2**answers

833 views

### Mathematical computer desk [closed]

D. Gibb, from the Mathematical Laboratory, University of Edinburgh,
describes a Computer Desk in his book A course in interpolation and numerical integration for the
mathematical laboratory, G. Bell ...

**3**

votes

**1**answer

264 views

### Stability of Levinson-Durbin method for Toeplitz system solutions ?

How stable is Levinson-Durbin method for solution of systems of linear equations ?
I mean if condition number of matrix is $k$, does intermidiate steps involve matrixes
with higher condition number ...

**12**

votes

**0**answers

287 views

### Descartes rule of signs for a noncommutative polynomial in matrix variables

Recently, while studying certain notions of "averaging" a set of input matrices, I obtained a nonlinear polynomial in matrix variables. A simple example is
\begin{equation*}
\mathcal{G}(X) := X^n - ...

**3**

votes

**2**answers

364 views

### battleship permutation

Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship ...

**2**

votes

**2**answers

2k views

### Numerical Computation of arcsin and arctan for real numbers [closed]

I'm coding some numerical methods and I do not know what the correct analysis would be for choosing the implementation for $arcsin$ and $arctan$ for real numbers. Here's what I know:
Both functions ...

**0**

votes

**1**answer

143 views

### eigenvector update formula

Suppose that $B$ is a Hermitian matrix with one known eigenpair $(\lambda,v)$. (assume its the smallest or largest pair, if you like). Form the rank one update $B+\rho bb^{T}$.
Now I'm interested in ...

**3**

votes

**2**answers

226 views

### Convergence rate of an iterative process

I have the following iterative process
$$a_n=a_{n-1}(1-\phi(a_{n-1})),\quad 0< a_0<1,$$
where $\phi(x)$ is a continuous increasing function, $\phi(0)=0$, and if $x\in(0,1)$ then $0< ...

**4**

votes

**2**answers

282 views

### Evaluating a limit similar to the Euler constant

In the course of studying a certain complex-valued functional equation, I have had a need to evaluate the following limit:
$$\gamma_\mathcal{T}=\lim_{n\to\infty}\left(-\frac{i}{2}\sum_{k=1}^n ...