All Questions
1,732 questions
1
vote
0
answers
290
views
Map Transformation to Force Convergence to Unique Fixed Point
Is there a transformation $\mathcal{T}$ of maps $\mathbb{R}_{{\geq}0}^{n} \rightarrow \mathbb{R}_{{\geq}0}^{n}$ with the following property?
If a map $F : \mathbb{R}_{{\geq}0}^{n} \rightarrow \mathbb{...
- 105
1
vote
0
answers
463
views
Splitting wave equation for application of CPML
A recent paper (Roden and Gedney, 2000) proposed the application of a Convolutional Perfectly Matched Layer (CPML) to approximate free-field conditions for Finite-Difference Time-Domain (FDTD) ...
- 157
1
vote
0
answers
165
views
Uncertainty on sum of values sampled from unknown probability distribution function
I am dealing with a Monte-Carlo simulation which provides me with a value $x$ as a result. I can run the simulation $n$ times, which gives me $n$ values. I don't know in advance what the probability ...
- 11
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
1
vote
0
answers
393
views
iterated characteristic polynomials
If I have $N$ $M\times M$ symmetric positive definite matrices $A_i$ and an $N\times N$ positive semi-definite symmetric matrix B, let the $N\times N$ matrix $C_{ij}(\lambda)=B_{ij}$ for $i\ne j$ and $...
- 11
1
vote
1
answer
152
views
Linear interpolation vs L2-projection
I'm reading the book "The Finite Element Method: Theory, Implementation, and Applications" by Larson and Bengzon. In the first chapters there are presented two methods for approximating ...
- 19
1
vote
1
answer
226
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 ...
- 105
1
vote
1
answer
154
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.
0
votes
1
answer
1k
views
For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?
Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
- 135
0
votes
1
answer
769
views
Proving that the eigenvalues of a certain matrix product are positive
Let $A$ be an $m \times n$ matrix, and define:
\begin{align*}
U &= {\rm diag} \{ \frac{1}{\beta_j} \}, \beta_j = \sum_{k=1}^m |a_{kj}|, j = 1 \dots n \\
V &= {\rm diag} \{ \frac{1}{\alpha_i} \}...
- 3
0
votes
1
answer
320
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
0
votes
2
answers
303
views
Benchmark Systems for ODE Solvers - Reference Request
I would like to have a basic models as a ground truth for the numerical solvers. I am looking for systems which have available analytic solution. As an example I know that the closed form solution of ...
- 135
0
votes
1
answer
255
views
Numerical methods for solving a hyperbolic nonlinear PDE
What type of numercial methods are there to solve PDE of the sorts of:
$$f(x,t,u(x,t))u_{xx} - g(x,t,u(x,t))u_{tt} = F(x,t,u(x,t))$$
$$u(x,0)=G_1(x) , \frac{\partial u(x,0)}{\partial t}=H_1(x) ,u(0,t)...
- 1,594
0
votes
1
answer
2k
views
How to determine the distance between two matrices under the meaning of a matrix function? [closed]
Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a ...
- 197
0
votes
1
answer
359
views
An Infimum Question [closed]
Is it true that
$$\inf_{t,x,y\in\mathbb{R}}\max\left(\left|x-1\right|+\left|tx-1\right|,\left|y-1\right|+\left|ty-2\right|\right)=1/3?$$
Thanks.
- 95
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
0
votes
1
answer
539
views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
0
votes
1
answer
226
views
Fractional values in linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
0
votes
1
answer
144
views
Maximize function on rotation matrices [closed]
Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively:
\begin{equation}
Q=
\...
0
votes
1
answer
540
views
Computing spectrum of convex combination of SPD matrices given individual spectral decompositions
Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K_{i}\right\} _{i=1}^{M}, U_{i}D_{i}U_{i}^{T}=K_{i},\quad i=1,\dots,M,$$ ...
- 133
0
votes
1
answer
338
views
Is spectral properties a general term for condition number?
I am reading an article about solving large sparse linear systems, in this paper it’s said that most of the iterative methods to solve $Ax = b$ are very much influenced by the spectral properties of ...
- 253
0
votes
1
answer
98
views
What is exponentially fitted osculating straight line?
While reading an article about iterative methods for solving nonlinear equations I can't understand what is exponentially fitted osculating straight line. Could someone please briefly explain this ...
- 163
0
votes
3
answers
7k
views
Find an $N$-dimensional vector orthogonal to a given vector
I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only ...
0
votes
3
answers
2k
views
Polynomial Regression/Least Squares
I have a couple questions on the same topic:
1) Does ordinary linear least squares have a generally defined confidence interval. I know that you can determine the confidence interval of each term, $\...
- 9
0
votes
2
answers
178
views
Inversion formula for discrete sine and cosine transforms
$\newcommand{\wh}[1]{{\widehat{#1}}}
\newcommand{\R}{{\mathbb{R}}}
$I am looking for a proof of the inversion formulas for the discrete sine and cosine transforms, i.e. a proof of the fact that these ...
- 113
0
votes
1
answer
36
views
Benefit of adding a trivial constraint to ILPs
let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...
- 13.2k
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
0
votes
1
answer
131
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
0
votes
1
answer
214
views
How do you call a linear programming problem when the solution should be "constrained" to a norm?
(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...
- 143
0
votes
1
answer
320
views
Sub optimal algorithm for linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
0
votes
1
answer
39
views
Gluing simplices through a common point/ realisation of a convex simplicial polytope
Given $m≥d+1$
a positive integer, is it always possible to find m d-dimensional simplices $\Delta_i=\mathrm{Conv}(M,V_{i,1},…,V_{i,d})$ such that
1) they all share the common vertex M
2) the ...
- 1,435
0
votes
1
answer
309
views
Fast and reliable positive real root of cubic [closed]
I know that in a cubic equation $ax^3+bx^2+cx+d=0$ holds $a,b>0$, and $d<0$, so there exists exactly one positive real root. I can solve for all of the roots, no problem, but I want to ...
user68635
0
votes
1
answer
212
views
How to find out if a polytope contains a sphere?
Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope?
Thanks!
- 225
0
votes
2
answers
636
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 ...
- 9
0
votes
1
answer
130
views
Cascading minimization problems
Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. ...
- 57
0
votes
2
answers
891
views
Find both maximum and minimum values in linear programming problem
Hi all. I have a linear programming problem where I need to find both maximum and minimum values of the objective function. The optimal points are not relevant.
Is there an efficient way to do so?
- 57
0
votes
1
answer
1k
views
Frequency calculation using fourier transform [closed]
How to calculate the frequency of an audio file using Fourier Transform
- 9
0
votes
2
answers
436
views
Discrete Wavelet Transform and L2 Basis
Using the mother wavlet $phi$ one obtains an orthonormal basis $\phi_{j,k}(x):=2^{j/2}\,\phi(2^j\,x-k)$of L^2 (on the unit interval say). Given a function $f$ on can calculate the coefficients using ...
- 1,256
0
votes
2
answers
4k
views
Linear programming piecewise linear objective
I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:
max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$
$s.t. $
$|\...
- 3
0
votes
2
answers
2k
views
Finding the local/global minima of Shubert function
Consider the 2D Shubert function. As given in that page, the function has 18 global minima and several local minima. How can I find the (x,y) of all these minima? Any help appreciated. If it was a ...
- 121
0
votes
2
answers
4k
views
Convergence of iterative algorithm.
For quite a long time I'm trying to prove convergence of an iterative algorithm in case of a particular system of nonlinear equations.
Here are some characteristics of this system:
It consists of n ...
0
votes
1
answer
58
views
Integration algorithm and analytic property
This question is the continuation of the previous one.
In the article about the integration of analytical polynomial - time computable function $f(x)$ with the Taylor series $$f(x) = \sum_{n=0}^{\...
- 81
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
0
votes
1
answer
166
views
Matrices and vectors of intervals
I'm working on a project and think that matrices and vectors of intervals will be useful.
I'm aware about interval arithmetic, but there is little information on the internet, regarding matrices and ...
- 49
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 13.2k
0
votes
2
answers
131
views
Reshaping data vector into a matrix for deconvolution using a circulant matrix
Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means ...
- 879
0
votes
1
answer
212
views
Where can I find the paper by Tappert and Hardin on split-step Fourier transform method?
The split-step method is a numerical method that can be used to solve a nonlinear PDE (https://en.wikipedia.org/wiki/Split-step_method). Even Wikipedia does not refer to the original authors (F.D. ...
- 101
0
votes
1
answer
142
views
Least square error problem ill conditioning
I am trying to understand why I am getting an almost singular matrix in a problem I have.
The problem is a simple as
$$
\min_{X \in \mathbb{R}^{m,n}} \left\lVert AX - B \right\rVert_F^2
$$
Obvioulsy ...
- 115
0
votes
1
answer
171
views
Are root finding algorithms stable for bounded polynomials? [closed]
Suppose that we have a bounded polynomial defined on $[0,1]$. I think because it is just polynomial, root finding algorithms would easily and without any instability find all its roots. Am I right?
...
- 113
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 13.9k