Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

2
votes
2answers
249 views

Computing hypergeometric function of matrix argument

In the context of the Bingham probability distribution the ${ }_1F_1$ hypergeometric function of matrix argument naturally arises as a normalization constant of the probability distribution function. ...
6
votes
2answers
266 views

Rigorous numerics for maxima and minima (one variable)

Let $f:\mathbb{R}_0^+\to \mathbb{R}$ be defined by some combination of the four basic operations and square roots. (The argument of square-roots is assumed is to be non-negative, and the value of ...
1
vote
1answer
161 views

integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$. My goal is to find an ...
2
votes
0answers
207 views

eigenvalues of the sum of a stochastic matrix and a diagonal matrix

Let $D$ be a real diagonal matrix $D=diag(a_1,a_2,\ldots,a_n)$ with $a_1\le a_2\le\ldots\le a_n$. Assume that at least one of the $a_i$ is positive. Let $P$ be an irreducible, real, row-stochastic ...
3
votes
2answers
258 views

Questions on Discrete Exterior Calculus in numerial computing

I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics: (Discrete Exterious Calculus is the newly developed ...
1
vote
1answer
126 views

For what values of the parameter does this function have an elementary anti-derivative?

I am a grad student working on some independent research trying to derive some exact formulas for a particular class of power series. During my study I came across the following integral which would ...
2
votes
1answer
166 views

Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways: 1- Mark ...
4
votes
1answer
413 views

Hilbert Matrix and Approximation Theory

I was reading about the Hilbert matrix and Cauchy determinants: \[ \det \left[ \frac{1}{i+j-1} \right]_{i,j} \] By guessing where this determinant is $0$ or $\infty$ we can guess the right formula. ...
5
votes
0answers
242 views

Approximation by polynomials

The following is a well-known theorem (see e.g. The Chebyshev Polynomial by Rivlin): If $p(x) = x^n + a_{n_1} x^{n-1} + \ldots + a_0$, then $\max_{-1\leq x \leq 1} |p(x)| \geq 2^{1-n}$ for $n \geq 1$ ...
2
votes
1answer
133 views

Optimization problem

I'm trying to solve a very practical optimization problem and I think I hit a dead-end. There are $N$ products ($N \sim 50$). Each product can have a price $p_i$ in range between 1 and 40 dollars. ...
0
votes
1answer
85 views

Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$. $(x = 0 \wedge y = 1) \vee (x \neq 0 ...
1
vote
0answers
69 views

Orthogonal projection of discontinuous piecewise polynomial space in energy scalar product

Let $I = [0,1]$ be the unit interval Let $I$ be partioned into $n$ closed subintervals $(I_j)_J$, each of length $1/n$. Let $X_{DC} = \{ v \in L^2[0,1] | 1 \leq j \leq n : v_{|I_j} \in \mathcal P_1( ...
9
votes
2answers
643 views

Rigorous numerical integration

I need to evaluate some (one-variable) integrals that neither SAGE nor Mathematica can do symbolically. As far as I can tell, I have two options: (a) Use GSL (via SAGE), Maxima or Mathematica to do ...
0
votes
2answers
199 views

Proof that polynomial evaluated at roots of unity is DFT [closed]

Hello All, I hope I am not abusing the forum here. I am just trying to understand the efficient implementations of the fast fourier transform. My reading and searching has led me to understand that ...
13
votes
1answer
2k views

The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't ...
4
votes
1answer
232 views

best rank r approximation for non-Frobenius norm

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...
2
votes
2answers
1k views

Finding the formula for Bezier curve ratios (hull/point : point/baseline)

Given a cubic Bezier curve defined by points p₁, p₂, p₃, and p₄, a point B on that curve at some t value (where 0 ≤ t ≤ 1), a point A on the line (p₂ — p₃) at distance ratio t from p₂, and a point C ...
1
vote
1answer
121 views

Recommendations for binomial system solver

I am interested in solving binomial systems of the form $$ \begin{cases} a_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} + b_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} &= 0 \\\\ ...
3
votes
1answer
124 views

approximation methods in integral equations

Recently I was reading about integral equations and I am a beginner in it. There was a constant reference to the non-availability of methods to find the exact solutions and hence lot of approximation ...
1
vote
1answer
200 views

How are real-analytic functions encoded in computer algebra?

I would like to know how are encoded the real-analytic functions on the interval by the computers. When I think in a real-analytic function I just think in a composition of the ''typical'' analytic ...
4
votes
1answer
528 views

Matrix perturbation theory

I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...
2
votes
0answers
196 views

Convergence rate of iterated nonlinear equations?

For $i=1, \dots, n$ ($n$ could be large) we have variables $x_i$ and $y_i$ relating to probability bounds s.t. $x_i, y_i \geq 0, x_i+y_i \leq 1 \; \forall i$. Each $i$ has a constant $\theta_i$, and ...
2
votes
0answers
171 views

Heat transfer coefficients - correlation equations for Nusselt number - vertical pipe

I need a heat transfer coefficient applicable to free convection of water INSIDE a vertical pipe. I have the correlation equation from Churchill and Chu, but it is only valid for D/L>=35/Gr^(1/4), ...
3
votes
1answer
94 views

Kronecker-structured matrix kernel

Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix $$ M= \begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix} $$ has size ...
2
votes
1answer
217 views

Approximation theory under $L_1$-error

Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error? Formal definitions for functions of one variable are below. Let $C$ ...
2
votes
0answers
132 views

Radius of convergence to be proved more precisely (differential equation)

There is a differential equation in polar coordinates: $r'^2+r^2=(kt)^2$, $r(t=0)=0$, k- Const. It is possible to get a solution which is a power series (see below). However, I am looking for an ...
3
votes
1answer
287 views

Lebesgue constant as condition number of polynomial interpolation

Let $T = \{ x_0,\ldots,x_n \}$ be a set of $n+1$ different points in the real interval $[a,b]$. Let $X_T$ be the associated interpolation operator on $C[a,b]$: it takes a function $f \in C[a,b]$ into ...
4
votes
1answer
841 views

Smoothing L1 norm, Huber vs Conjugate

I'm trying to minimize a convex (not necessarily strictly convex) function involving an L1 norm (similar to lasso), which makes it non-differentiable at some points. So I'd like to smooth it and treat ...
4
votes
0answers
47 views

Recovering Shared Eigenvector Set

Suppose we are given a set of $M$ pairs $\{(\vec{x}^{(i)},\vec{y}^{(i)})\}$, with $\vec{x}^{(i)}\in\mathbb{R}^N$, $\vec{y}^{(i)}\in\mathbb{R}^N$, $M\gg N$ such that $\vec{y}^{(i)} = Q^{(i)} ...
6
votes
2answers
720 views

Approximating erf by tanh

It appears to be well-known that $\tanh(x)\le \mathrm{erf}(x)$ on $[0,\infty)$. It's off-handedly mentioned here, for example. Where can I find a formal proof? On the one hand, it's hard to imagine ...
2
votes
0answers
129 views

integrate square of bessel 1st and 2nd kind

Has anyone ever solved the integral of square of Bessel and Neumann functions? This is for standing wave analysis on a cylindrical object. I need to integrate $(AJ(kr) + BY(kr))^2$ from $r=a$ to ...
1
vote
0answers
75 views

Integrating B-Spline composed with log

If $f$ is a real B-Spline and $a, b$ are real numbers, then is there a numerically stable way to evaluate the following expression? $\int_a^b f (\log x) \mathrm{d}x$
16
votes
3answers
841 views

Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute $f(x)$. The input consists of the digits of $x$ and the output of a rational number approximating $f(x)$. A function $f$ is called ...
5
votes
0answers
139 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
13
votes
2answers
299 views

Condition number of matrix after partial orthogonalization

I'm wondering about which bounds one can put on the condition number of a $n\times n$ square matrix which is obtained from another $n\times n$ square matrix by orthogonalizing the first $m < n$ ...
3
votes
0answers
137 views

Upper bound on integrals of Legendre polynomials

Hi, If $P_n(x) $ is unnormalized shifted Legendre polynomial, and $g_{n,m}(x) = \int_0^x P_n(x_1)x_1^m dx_1, n>m $ then what is the upper bound $ |g_{n,m} (x)|_{max} , x\in (0,1) $ as a function ...
5
votes
0answers
420 views

Parabolic cylinder functions - explicit estimates?

I need estimates for the parabolic cylinder functions $U(a,z)$ (first studied by Whittaker). Most work in the literature focuses on $a$ real. As it happens, I am interested in $U(a,z)$ on a strip in ...
7
votes
2answers
315 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
801 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
314 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
136 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
138 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
272 views
4
votes
1answer
491 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 ...