All Questions
1,732 questions
8
votes
4
answers
338
views
Scaling a set of reals to be nearly integers
A version of this question was previously asked on MSE. I'll mention progress below.
A geometric construction I'm exploring
leads to a set $R$ of $n$ positive real numbers, for example:
$$
R = \{ \pi,...
- 151k
8
votes
1
answer
736
views
Sharpest bound on the zero free region of $\zeta^{\prime}$?
I'm interested in calculating all of the zeroes of the first derivative of the Riemann $\zeta$ function up to an arbitrary height. I know that (on the RH), all of these zeroes will have real part $\ge ...
- 83
8
votes
4
answers
6k
views
Solving a System of Quadratic Equations
I have many polynomial equations in many variables which I want to jointly minimize (in a mean square sense, but you could pick a different reasonable measure which favors anything where all ...
- 1,547
8
votes
2
answers
3k
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 $\phi^{-...
- 93
8
votes
2
answers
2k
views
error estimates for multi-dimensional Riemann sums
Suppose that $f$ is a continuous function of bounded variation from $R^2$ to $R$ that's negative outside of some bounded set, and let $F=\max(f,0)$. Let $S_n$ be the Riemann sum for the integral of $F$...
- 19.7k
8
votes
2
answers
2k
views
Algorithm for solving systems of linear Diophantine inequalities
So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...
- 3,079
8
votes
1
answer
330
views
Compute an arbitrary decimal place of $\pi$
Is there a method to find the value of the $n$-th decimal place of $\pi$ which is more efficient than having to compute all decimal places before as well?
- 83
8
votes
2
answers
361
views
Computational methods for dealing with geometrically complicated solid boundaries in fluid-air interface problems
Hello,
I am a PhD student who does not have extensive computational experience seeking advice from those experienced with computational modelling as to which method would be most appropriate for ...
- 147
8
votes
3
answers
859
views
Books and resources on PDEs that use Mathematica and Matlab
Can you recommend some reference books that use software like MATLAB and Mathematica to deal with the basic topics in
analysis of PDE (the ones you can find in Strauss' book Partial Differential ...
user60665
8
votes
1
answer
3k
views
Algorithm to produce random number with a gamma distribution
I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation.
I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...
- 183
8
votes
2
answers
3k
views
Discrete gradient on point clouds
I am interested to know some ways to approximate discrete gradient if you have a function on point clouds in 2D or 3D.
If you have a function defined on a grid, it well known that you can use a ...
- 81
8
votes
1
answer
7k
views
Upper bound on largest eigenvalue of a real symmetric $n \times n$ matrix with all main diagonal entries positive, everywhere else nonpositive
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 ...
- 83
8
votes
2
answers
4k
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: $...
- 500
8
votes
2
answers
950
views
Best known bounds on (border) ranks of small matrix multiplication tensors?
The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. ...
- 7,633
8
votes
1
answer
1k
views
Gaps between roots of trigonometric polynomials
[Cross-posted from Math.SE because I got no responses there.]
Given a polynomial in $e^{\mathrm{i}k t}$ of the form
$$ p(t) = \sum_{-n\leq k\leq n} c_k e^{\mathrm{i}k t} $$
with $\bar c_{-k} = c_k$, ...
- 416
8
votes
3
answers
1k
views
Is there a stable algorithm for polynomial division (in several variables)?
Suppose you have a homogeneous ideal $I$ inside the algebra $\mathbb{C}[x_1,...,x_d]$ of complex polynomials in $d$-variables. Can one find a basis for $I$, say $\{f_1,...,f_k\}$, such that every $h \...
- 550
8
votes
1
answer
363
views
is there any such result about Bernstein polynomials?
It is well known that for any lipschitz function $f:[0,1]\rightarrow [0,1]$, we can approximate it
by $\sum_{i=1}^n f(i/n) {n\choose i} x^i (1-x)^{n-i}$, and the $L_\infty$ error is $O(1/\sqrt{n})$. ...
- 401
8
votes
4
answers
2k
views
Numerical integration of legendre polynomials
I hope that numerical questions are also permitted here.
I want to expand a smooth functions $f \in C^{\infty}$in terms of Legendre polynomials. Thus I need to calculate integrals of the form $\int_{-...
user54300
8
votes
1
answer
354
views
Are there any explicit probability conserving solvers for Pauli equation?
I know that there exist probability conserving explicit solvers for time-dependent Schrödinger's equation, for example, Visscher's one.
But when I tried to take into account spin and magnetic field (...
- 285
8
votes
3
answers
372
views
Regularized linear vs. RKHS-regression
I'm studying the difference between regularization in RKHS regression and linear regression, but I have a hard time grasping the crucial difference between the two.
Given input-output pairs $(x_i,y_i)...
- 41
8
votes
1
answer
213
views
Fast Fourier Transforms for non-trigonometric bases
The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
- 81
8
votes
1
answer
1k
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}
v_{1,0}&v_{2,0}&\dots&...
- 959
8
votes
1
answer
669
views
How to evaluate binomial coefficients efficiently and as correctly as possible?
This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer.
The reason why I ask is ...
- 2,054
8
votes
2
answers
577
views
A competitive root finding game
Inspired by a question about bisection I wondered about the following: The are two players X and Y and a moderator Z who knows two (random,independent, uniformly chosen) hidden reals $x$ and $y$ from ...
- 30.1k
8
votes
2
answers
8k
views
Numerically most robust way to compute sum of products (standard deviation) in floating-point?
I stumbled across a paper by Welford (1962), where he proclaims a method that should compute the standard deviation numerically more robust than the naive algorithms (http://www.jstor.org/stable/...
- 191
8
votes
2
answers
246
views
Are sums of 0-1 Pareto efficient vectors Pareto efficient?
Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...
- 388
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 361
8
votes
0
answers
481
views
Problems where Conjugate gradient works much better than GMRES
I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
- 489
8
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
- 133
7
votes
5
answers
5k
views
What is an extragradient method?
I've searched Google, but it seems that only research journal papers appear in search results, where some new, improved, or specialized extragradient method is discussed. I've also searched Wikipedia ...
- 357
7
votes
2
answers
379
views
Alternating binomial Dirichlet series
I have come across the following deceptively simple expression:
$$ H_n^s=\sum_{j=1}^n(-1)^{j-1}\left(\begin{array}{c}n\\j\end{array}\right)j^{-s} $$
We have (using eg mathematica, though probably ...
user25199
7
votes
2
answers
387
views
Is it possible to prove unboundedness of 3rd order ODE?
Consider the 3rd order ODE
$$\dddot{x}+A\ddot{x}-\dot{x}^{2}+x=0$$ where $\dot{x}\equiv \frac{dx}{dt},\ddot{x}\equiv \frac{d^{2}x}{dt^{2}}, etc$. $A$ is a constant.
If we multiply this equation by $\...
- 213
7
votes
2
answers
909
views
Formula for volume of a convex polytope
So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
- 81
7
votes
2
answers
220
views
Well-balanced covering of transpositions in $n$ elements
Let me denote $X_n$ the set of transpositions in $n$ elements. Equivalently, $X_n$ is the set of doubletons in $[1,n]\times[1,n]$. The cardinality of $X_n$ is $N=\frac{n(n-1)}{2}$.
If $f:{\mathbb Z}/...
- 52.3k
7
votes
2
answers
7k
views
Computational complexity of calculating the nth root of a real number
Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...
- 385
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
7
votes
3
answers
1k
views
How to numerically compute $x \ln x$ and related functions near $0$?
I was recently trying to find a numerical solution to a thermodynamics problem and the expression $x\ln x$ appeared in one of the computations. I did not have to find its value very near $0$, so the ...
- 3,738
7
votes
1
answer
360
views
Does the Hirsch conjecture hold for $n < 2d$?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
- 7,857
7
votes
4
answers
1k
views
Reasonable "Random" matrices to test numerical algorithms
Hello,
in numerical analysis, it is common to compare the behavior of different algorithms, and of different implementation of algorithms. This occurs not only on the theoretical level, but also on ...
- 5,327
7
votes
1
answer
289
views
A centralised website for computational attempts in graph theory and metric geometry?
The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph theory ...
- 883
7
votes
3
answers
2k
views
What is the right citation for the power iteration method to find eigenvalues?
What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...
- 171
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
- 1,890
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
7
votes
2
answers
1k
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 ...
- 285
7
votes
1
answer
819
views
Has this generalization of a determinant (assigning multiplicities to the rows) been studied?
I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:
Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
- 1,509
7
votes
2
answers
372
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 ...
- 20.2k
7
votes
1
answer
191
views
Reporting inconclusive experimental searches
In many areas of mathematics it is informative to conduct numerical experiments.
But, it not uncommon that the searches do not lead to the examples or data one was hoping for. Since the numerical ...
- 2,901
7
votes
2
answers
385
views
Solution to at least one ODE in a family of ODE's
In my research I have stumbled across the following 1st order complex differential equation for smooth functions $\eta:\mathbb{R}/2\pi\mathbb{Z}\to\mathbb{C}-\lbrace0\rbrace$ defined on the circle,
$$...
- 17.5k
7
votes
2
answers
697
views
Local positivity of solutions to linear differential inequalities (Chaplygin's theorem)
According to the entry "Differential inequality" of the Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Differential_inequality
the following result is due to Chaplygin (1919)...
- 1,371
7
votes
1
answer
505
views
Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently
What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and ...
- 493