All Questions
1,732 questions
7
votes
1
answer
254
views
Numerical method for simultaneous computation of eigenvalues of a family of commuting matrices
I have a problem where I have $n$ commuting matrices $M_1,\dots,M_n$. It is a well-known fact that commuting matrices are simultaneously diagonalizable/triangularizable. I need to find the eigenvalues ...
7
votes
1
answer
374
views
Sampling uniformly from the vertices of a polytope
I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...
- 15.4k
7
votes
1
answer
333
views
Can we estimate the error $\left| \frac{1}{N^2} \sum f ( \{ \sqrt{2} m + \sqrt{3} n \} ) - \int_0^1 f(x) \, dx \right|$?
As a computer experiment I did a few Riemannian sums to see if I could quantify the density statement $\overline{\mathbb{Q}(\sqrt{2}, \sqrt{3})} = \mathbb{R}$ :
$$ \Big| \frac{1}{N^2} \sum_{0 \leq m,...
- 22.8k
7
votes
3
answers
2k
views
Euler Schemes in Stochastic Differential Equations
So i am trying to understand what happens in Implicit (backward) and Explicit (forward) Euler in Stochastic Differential Equations
I'll start with explicit. Say I have the following SDE known as ...
- 93
7
votes
1
answer
449
views
Can I find the gap between the two least eigenvalues of this special matrix A(t)?
I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal non-...
- 103
7
votes
2
answers
314
views
Finding a low-degree polynomial vanishing on half the zeroes of a polynomial system
Let $f(x)$ be a real polynomial of degree $2d$ without real roots. Let the complex roots be $z_1$, $\bar{z_1}$, $z_2$, $\bar{z_2}$, ..., $z_d$, $\bar{z_d}$ with $z_i$ in the upper half plane. Let $g(x)...
- 156k
7
votes
1
answer
298
views
Computing a determinantal representation of a bivariate polynomial
Let $p \in \mathbb R [x,y,z]$ be a homogeneous irreducible polynomial of degree $d$. From Dickson in 1920 we know that there exists $A$, $B$ and $C$ such that
$$\det (Ax + By + Cz) = c p(x,y,z)$$
...
- 3,217
7
votes
1
answer
247
views
Add a multiple of $I$ to a matrix to minimize its operator norm
Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$?
Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity.
The corresponding problem for the ...
- 20.2k
7
votes
1
answer
224
views
A polytope with a bound on the sum of any $k$ variables
Let $2\le k\le n-1$ and define the polytope
$$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n :
-1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$
There ...
- 37.7k
7
votes
1
answer
197
views
Compute only selected components of an eigenvector
I am wondering whether it is possible to compute portions of the eigenvectors of a given (possibly very big) matrix. More formally, consider the eigenvalue problem $\mathbf{Ax} = \lambda \mathbf{x}$, ...
- 91
7
votes
1
answer
318
views
Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?
Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
- 325
7
votes
1
answer
4k
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 ...
- 205
7
votes
2
answers
3k
views
Factorizing a block symmetric matrix
Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...
- 20.2k
7
votes
1
answer
356
views
Is there any sort of higher-order SVD (quadratic and above) for dimensionality reduction?
(Posted this on math.stackexchange and cross.correlated over more than a week ago, but didn't get an answer, and this is a question in my research so this seems like it might have been the better ...
- 141
7
votes
1
answer
590
views
Discontinuity of solutions to approximation schemes in the Barles-Souganidis framework
I have attached pg. 275 and pg. 276 of [BS91]. My concern is with the claim (2.7) on pg. 276. To prove this claim, I require the following additional assumption, which is not made by the authors:
...
- 331
7
votes
3
answers
3k
views
Algorithm for the smallest (algebraic) eigenvalues of a symmetric (sparse) matrix
Hi,
I'm looking for a way to get the negative eigenspace of a large (sparse) symmetric matrix. This matrix is basically a discretized version of the operator $-\Delta + V$, $V$ negative, on some ...
- 411
7
votes
1
answer
803
views
Random, Linear, Homogeneous Difference Equations and Time Integration Methods for ODEs
Most methods (that I know of) of numerically approximating the solution of ODEs are "general linear methods". For this type of method, the so-called 'linear stability' is examined by applying the ...
- 103
7
votes
1
answer
2k
views
On Clenshaw's summation formula
When one has a finite sum of the form
$S=\sum_{k=0}^{n}{c_k F_k(x)}$
where $F_k(x)$ satisfies a two-term recurrence relation
$F_{k+1}(x)=\alpha_k F_k(x)+\beta_k F_{k-1}(x)$
the standard algorithm ...
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
- 81
7
votes
3
answers
490
views
accelerating convergence of a class of sequences
Do any of the standard methods of acceleration convergence of series, when applied to
the series $1 - 1 + 1/2 - 1/2 + 1/3 - 1/3 + ...$, give convergence to 0 with error $o(1/n)$?
I tried applying ...
- 19.7k
7
votes
1
answer
359
views
How to estimate the pressure?
I have a finite collection of diffeomorphisms $g_1,\cdots,g_n$ taking the unit interval $I$ to disjoint subintervals $I_1, I_2,\cdots,I_n$. If $G$ is the semigroup they generate, the limit set of $G$ (...
- 2,562
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
7
votes
0
answers
317
views
An inequality which involves a sum of integrals
Please help me to prove
$$
\sum\limits_{j=2}^n \frac{1}{j^\alpha (j-1)^\alpha} \int\limits_{j-1}^j \frac{dx}{x^{1-\alpha}(n-x)^\alpha} \leq \int\limits_0^1 \frac{dx}{x^{1-\alpha}(n-x)^\alpha},\quad \...
- 71
7
votes
0
answers
209
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 ...
- 619
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
6
votes
2
answers
3k
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 ...
- 6,541
6
votes
4
answers
7k
views
Why do we want to have orthogonal bases in decompositions?
In the decompositions I encountered so far, we all had orthogonal set of bases. For example in Singular Value Decomposition, we had orthogonal singular right and left vectors, in [discrete] cosine ...
- 497
6
votes
3
answers
502
views
Approximating derivatives between gridpoints
Suppose we have a grid (possibly irregular) of $N$ function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more).
What would be a good way to ...
- 177
6
votes
2
answers
1k
views
Are the banded versions of a positive definite matrix positive definite?
Consider $M$, a positive definite matrix. Let $M^{(1)}$ be the diagonal matrix which agrees with $M$ on the diagonal ($M_{ii}=M^{(1)}_{ii}$). We have that $M^{(1)}$ is positive definite because it is ...
- 375
6
votes
5
answers
2k
views
Restricted Three-Body Problem
The movement of a spacecraft between Earth and the Moon is an example of the infamous Three Body Problem. It is said that a general analytical solution for TBP is not known because of the complexity ...
- 103
6
votes
6
answers
3k
views
The maximum of a real trigonometric polynomial
Given the coefficients $a_0,\ldots,a_N$, $b_1,\ldots,b_N$ of a real trigonometric polynomial:
$ f(x) = a_0 + \sum_{n=1}^N a_n \cos(nx) + \sum_{n=1}^N b_n \sin(nx) $
is there any efficient way to ...
- 531
6
votes
1
answer
944
views
Approximately Invert x^x
What is the best asymptotic approximation of the inverse $x=g(y)$ of $y = x^x$ for large $x$? [Clearly, if $x>e$, then $f(x) > e^x$ implies $g(x) < \log x$.]
- 73
6
votes
3
answers
3k
views
minimize the sum of absolute eigenvalues
Hi,
We have a real symmetric matrix M with diagonal elements 0's, the eigenvalues and eigenvectors of M are computed.
Now we wish to change its diagonal elements arbitrarily to minimize the sum of ...
6
votes
1
answer
617
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
- 6,367
6
votes
2
answers
539
views
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
I've been working on the following polynomial approximation problem. I want to find the optimal Chebyshev approximation of the rational function $\frac{1}{1-x}$ on the real interval $x\in[-\rho, \rho]$...
- 63
6
votes
3
answers
1k
views
Dependence of error on mesh for Riemann sums
Suppose $f$ is continuous on $[a,b]$ with $I = \int_a^b f(x)\: dx$,
and for every $\epsilon > 0$ let $\delta(\epsilon)$ be the largest
$\delta > 0$ such that every Riemann sum arising from a ...
- 19.7k
6
votes
6
answers
2k
views
Smoothing out Noisy Data
I recently launched a rocket with an altimeter that is accurate to roughly 10 ft. The recorded data is in time increments of 0.05 sec per sample and a graph of altitude vs. time looks pretty much ...
- 99
6
votes
1
answer
913
views
Resultant of linear combinations of Chebyshev polynomials of the second kind
The Chebyshev polynomial $U_n(x)$ of the second kind is characterized by
$$
U_n(\cos\theta)=\frac{\sin(n+1)\theta}{\sin(\theta)}.
$$
It seems that
$$\operatorname*{Res}_x \left( U_n(x)+tU_{n-1}(x),\...
- 437
6
votes
2
answers
1k
views
Linear programming is continuous
Consider an arbitrary linear program:
$$\max \vec c \cdot \vec x$$
subject to:
$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$
Assume that this program is feasible and bounded. ...
- 884
6
votes
3
answers
285
views
Finding a solution to a simple geometric set of equalities
Let $p_1,\dots,p_n$ be a collection of points in the plane $\mathbb{R}^2$ and let $a$ be a positive number such that $a<1$. Is there a good numerical algorithm to find points $x_1,\dots,x_n$ in ...
- 4,049
6
votes
2
answers
920
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 &...
- 1,568
6
votes
3
answers
2k
views
Conjugate Gradient for a "slightly" singular system.
Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by ...
- 617
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
6
votes
3
answers
632
views
Appropiate models of numerical computation
Hello,
in contrast to the more discrete part of computational mathematics (cryptography, combinatorial computation), numerical mathematics seems to ignore typical questions of theoretical computer ...
- 5,327
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
1
answer
647
views
How can I efficiently find the "simplest" rational in an interval?
For a hobby software project I am working with exact rational arithmetic, as it happens this produces numbers $\frac{n}{k}$ of huge size even after reducing them, I am searching for an efficient ...
- 163
6
votes
3
answers
2k
views
Estimating the variance of a discrete normal distribution
Let $f(x; \sigma) = \frac{1}{\sigma\sqrt{2\pi}}\cdot e^{-\frac{x^2}{2\sigma^2}}$ be the probability density function of a normal distribution $\mathcal{N}(0, \sigma^2)$. We consider a discrete normal ...
- 167
6
votes
2
answers
643
views
How to estimate the Haar measure on $G_2$
I have a sequence of real numbers. I want to know whether this sequence looks like the traces in the standard representation of a random sequence of elements of $G_2$. (Here random is according to the ...
- 148k
6
votes
3
answers
2k
views
A simple infinite dimensional optimization problem
I'd be grateful for a reference for the following result, which I believe to be true, and
should be well-known.
Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
- 520
6
votes
2
answers
287
views
Computing certain integrals over high-dimensional polyhedra
Let $\delta>0$ be a small real number and consider the $k$-dimensional region consisting of points for which
$$\delta\leq x_1\leq x_2\leq\ldots \leq x_k$$
and
$$x_1+\ldots+x_k\leq 1.$$
I am ...
- 761