Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

7
votes
2answers
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
4answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
284 views
4
votes
1answer
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
1answer
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
7answers
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
1answer
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
2answers
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
2answers
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
3answers
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
1answer
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
1answer
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
1answer
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
0answers
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
4answers
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
1answer
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
0answers
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
1answer
417 views

Numerical Methods for ODEs - History

Wikipedia presents a timeline of important developments in Numerical Methods for ODEs, namely: ...
-5
votes
2answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
4answers
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
0answers
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
0answers
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
2answers
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
4answers
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
2answers
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
2answers
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
1answer
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
2answers
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
2answers
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 ...