All Questions
783 questions
1
vote
0
answers
34
views
Slope assertion in Cholesky on digital computers
For a real symmetric positive definite linear system
$$ A \cdot x = b, $$
solved using Choelsky with forward- and backward-substitution, we know it for the numerical approximation $\tilde{x}$ to $x$ ...
- 63.9k
3
votes
2
answers
276
views
Practical symmetric equivalent to QR factorization updates
As we know, the QR-factorization $Q\cdot R=A$ of any real symmetric $n \times n$ matrix $A$ with full rank is unconditionally numerically stable. Further, when A is rank-1-updated, the factorization ...
- 20.2k
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
1
vote
1
answer
59
views
Does norm of discrepancy decrease monotonously in CGLS/CGNR
I am the author of the package for tomographic reconstruction https://github.com/kulvait/KCT_cbct I have implemented CGLS/CGNR , algorithm which applies conjugate gradients on normal equation
$$
A^\...
- 151
6
votes
2
answers
463
views
Spectrum of operator involving ladder operators
The ladder operator in quantum mechanics are the operators
$$a^\dagger \ = \ \frac{1}{\sqrt{2}} \left(-\frac{d}{dq} + q\right)$$
and
$$a \ \ = \ \frac{1}{\sqrt{2}} \left(\ \ \ \!\frac{d}{dq} + q\...
- 42.8k
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 4,219
1
vote
1
answer
331
views
Eigenvalues of a circulant: DFT or Inverse DFT Convention?
Currently, most engineering texts (and webpages including Wikipedia) define forward discrete Fourier transform with a negative sign on the exponential. This is a convention and the inverse discrete ...
- 188k
1
vote
1
answer
426
views
Extracting eigenvalues of a circulant matrix using discrete Fourier matrix
The eigenvalues of a circulant matrix $C$ can be extracted as $$
\Lambda=F^{-1} C F
$$
where the $F$ matrix is a discrete Fourier transform matrix and $\Lambda$ is a diagonal matrix of eigenvalues.
...
- 188k
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 128k
7
votes
2
answers
244
views
Finding $\theta$ such that at least one eigenvalue of $A(\theta)$ is real
Is there a known method to find a set of $\theta$ such that at least one eigenvalue of $A(\theta)$ is purely real?
Assume $A(\theta)$ is a real square matrix whose elements are linear functions of a ...
CommunityBot
- 1
3
votes
1
answer
181
views
The proof of the invertibility of $\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$
Suppose that $n$ is even. Any suggestion/appraoch to prove that $S=\Big( \sin\frac{8kl\pi}{2n+1} \Big)_{k,l=1}^\frac{n}{2}$ is invertible?
- 15.4k
3
votes
1
answer
370
views
The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$
What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ when $n$ is odd?
- 656
1
vote
0
answers
137
views
What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^{\frac{n-1}{2}}$ when $n$ is odd?
Suppose that $n$ is odd. The eigen values/eigenvectors of the skew-circulant matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ are successfully computed in this post.
Q. What are ...
- 1,355
3
votes
0
answers
173
views
Can the Jordan decomposition of a matrix be computed in a backwards stable way?
Let $PJP^{-1}$ denote the Jordan decomposition of $M$. The matrix $J$ is a direct sum of Jordan blocks; it is unique up to permutation of the Jordan blocks. The matrix $P$ is not unique.
There are two ...
- 4,943
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 63.9k
0
votes
0
answers
272
views
Finding the eigenvectors of a submatrix
Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...
- 4,058
1
vote
0
answers
47
views
Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?
EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...
0
votes
1
answer
82
views
Combining Dantzig-Wolfe and Benders decomposition
I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....
- 5,429
34
votes
3
answers
6k
views
Why is uncomputability of the spectral decomposition not a problem?
Below, we compute with exact real numbers using a realistic / conservative model of computability like Type Two Effectivity.
Assume that there is an algorithm that, given a symmetric real matrix $M$, ...
0
votes
1
answer
405
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
CommunityBot
- 1
0
votes
0
answers
232
views
How to analyse the range of eigenvalues of a symmetric and indefinite matrix?
Let $G$ be a symmetric and indefinite matrix defined as follows
$$ G := S - \begin{pmatrix} I_n & I_n \\ I_n & I_n \end{pmatrix},$$
where $S$ is a symmetric positive definite matrix of size $...
1
vote
0
answers
111
views
Solving a block tridiagonal system with diagonal perturbations
Say we have a block tridiagonal matrix, $T \in \mathbb{R}^{NL \times NL}$, with constant off diagonals, $\mathbf{B} \in \mathbb{R}^{L\times L}$, given by
$$
T = \begin{bmatrix} \mathbf{A}_1 & \...
- 2,821
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}}^*}\...
- 5,429
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
0
answers
94
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 5,429
17
votes
4
answers
6k
views
Why is fast matrix multiplication impractical?
I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication.
I read some content saying fast matrix multiplications are impractical because of large ...
- 13.1k
0
votes
1
answer
149
views
Need help with computational and numerical methods for solve equations
This is my first question on this community. I am a applied scientist, not a mathematician.
I have the following simplified problem:
Let $u: [0,1] \rightarrow \mathbb{R}_+$ a real valued function ...
- 1
0
votes
1
answer
74
views
$\det(HH’) = 0$ for nonnegative $H$
$H$ is an $n\times m$ matrix with non-negative coefficients and $n < m$. $H'$ is the transpose of $H$.
Are the following statements true?
If $\det(HH’) > 0$, the rows of $H$ define the edges of ...
- 3,186
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} & \...
- 12.9k
1
vote
0
answers
59
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 1
1
vote
1
answer
67
views
Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?
I asked the same on math.Stackexchange.
I have $n$ (say $n = 300$) vectors $v_1,\dots,v_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v_j$ I denote it's coordinates as $v_{j1},\...
- 34.3k
0
votes
1
answer
143
views
$\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem
Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...
- 5,429
1
vote
0
answers
38
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
- 11
3
votes
0
answers
122
views
Preconditioners for $Ax=y$ that rely on hierarchical statistical modeling
Solving $Ax=y$ exactly can be done as:
fit a linear autoregressive model by treating rows of $A$ as data
apply this model to $A^T y$
Imperfect predictive model corresponds to an approximate inverse ...
- 2,442
2
votes
0
answers
27
views
Solve sparse system with nested inverse
What is the most efficient way to solve an equation
\begin{align*}
(A\,E^{-1}\,C) x = b, \qquad A\in \mathbb{R}^{m\times n}, \, E \in \mathbb{R}^{n\times n}, \, C\in \mathbb{R}^{n\times m}
\end{align*}...
- 21
0
votes
1
answer
64
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
- 5,429
2
votes
2
answers
243
views
Sum over exponentiated bilinear form in finite-field vector space
Let $A$ be a linear map over the finite-field vector space $(\mathbb F_2)^n$, i.e., an $\mathbb F_2$-valued $n\times n$ matrix, not necessarily symmetric. I'm interested in the sum
$$Z(A) = \sum_{X\...
- 148k
2
votes
1
answer
227
views
Solving linear programming without solving linear programming
Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
- 9,501
2
votes
1
answer
372
views
Who called Farkas' fundamental theorem a lemma?
Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
- 188k
2
votes
0
answers
121
views
Proving some properties of the Landweber–Fridman iterates
$\newcommand\norm[1]{\lVert#1\rVert}$Let $B\in \mathbb R^{n\times n}$ be a symmetric and positive definite matrix. Assume that $x\in \mathbb R^n$ is the solution of $Bx=w$ for some given $w\in \mathbb ...
CommunityBot
- 1
2
votes
1
answer
508
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 12.9k
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
621
views
Tensor matricizations and their decompositions
Suppose we have a 4-index tensor $t_{ijkl}$ (all 4 dimensions are equal size). We can make a matrix out of it by taking first and last two indexes as new indexes: $t_{ijkl} \rightarrow M_{ij, kl}$. ...
CommunityBot
- 1
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 ...
15
votes
2
answers
7k
views
Efficient rank-two updates of an eigenvalue decomposition (or more generally SVD)
Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al.1 and Bunch, et al.2 have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
- 4,713
0
votes
2
answers
556
views
Sparse dense matrix versus non-sparse dense matrix in eigenvalue computation
I have a matrix in the form of $2n\times 2n$ block matrix
$$
A = \begin{pmatrix}O& W\\
J& D\end{pmatrix}
$$
where, $O$ is an $n\times n$ zero-matrix; $W$ is a n-by-n diagonal matrix, $W = ...
- 2,821
1
vote
2
answers
3k
views
Low-rank factorization of SPD matrix
I have a symmetric positive definite (SPD) matrix $A$ that needs to be factorized as ${A=SS^{T}}$. However, using the Cholesky decomposition for this purpose is prohibitive in terms of computational ...
1
vote
0
answers
274
views
Find the eigenvectors from the QR algorithm in the unsymmetric case
It is possible to find many references describing the QR Algorithm with more or less refinements to approximate the eigenvalues of a square matrix $A\in\mathbb{R}^{n\times n}$.
I implemented a version ...
- 11