13

@user61318 and @JosephORourke, thanks for the advertisement for my book.
@chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (essentially the formula you wrote, along with some additional background) and the relevant references. However, in a broader sense much more is understood ...

11

Not in general. An explicit and elementary counterexample
is the sparse triangular matrix with $1$'s on the diagonal
and $-1$'s just above it: the inverse is the triangular matrix with
every entry on or above the diagonal equal $1$.

matrices na.numerical-analysis approximation-algorithms nonlinear-optimization numerical-linear-algebra

answered Aug 19 '13 at 17:37

Noam D. Elkies

69k1212 gold badges245245 silver badges330330 bronze badges

9

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated in $O(n^{1.5})$ with the algorithm given in
R.J. Lipton, D. Rose, R.E. Tarjan
Generalized nested dissection
SIAM J. Numer. Anal., 16 (1979), pp. 346-358
...

answered Oct 25 '18 at 18:14

Gjergji Zaimi

79.5k44 gold badges207207 silver badges371371 bronze badges

8

Before you can formulate your question precisely, you need a better notion of distance between two pictures of a set $S \subset \mathbb{C}$ (where in this case, $S$ is the union of Ford circles). If $\iota_1, \iota_2$ are pictures (bijections from square subsets $A_1, A_2$ of $\mathbb{C}$ to the unit square), then we can define distance as the Hausdorff ...

answered Nov 30 '15 at 15:50

Adam P. Goucher

11.3k22 gold badges4646 silver badges8888 bronze badges

7

Define the parent of a Ford circle to be the smaller of its two larger neighbors; then this parent relation defines the Stern–Brocot tree on the points of tangency of the circles. The path in this tree to a given real number is closely related to its continued fraction expansion. A path in the tree can be represented combinatorially by a binary sequence that ...

7

No polynomial-time algorithm exists, unless P=NP.
Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

graph-theory mg.metric-geometry computational-complexity combinatorial-optimization approximation-algorithms

6

This will answer your questions on $\delta$:
The case $\delta=1$, sometimes referred to as the ideal or optimal LLL-Algorithm, is the most natural way to define the swap condition between vectors after the length reduction step, as it forces to swap $b_k$ and $b_{k+1}$ if and only if its orthogonal 'emergence', i.e.
orthogonal distance of $b_{k+1}$ with ...

6

Below the line I address the question after "Update" about the relationship between volume and the number of lattice points. Since OP asks about conditions under which we can count the number of lattice points in $K$, let me point to a recent chapter by Barvinok, which has a lot of relevant information. Here are three special cases in which a positive result ...

5

Polynomials with a multiple root form a Zariski closed set (vanishing of the discriminant, which is a certain polynomial in the coefficients); hence, this set is nowhere dense, whereas its complement is dense. In other words, in any neighborhood of any point, "most" polynomials are nonsingular, and it's very unlikely one can detect the singularity unless the ...

5

This question is closely related to the so-called "condition number" of the B-spline basis. Basically, for a spline $f$ of some degree $p$ with a coefficient vector $c=(c_i)$, you generally have for any $q \in [1,\infty]$ that
$$
A_{p,q} \|c\|_{\ell_q} \le \| f \|_{L_q} \le B_{p,q} \|c\|_{\ell_q},
$$
and the smallest possible ratio $\kappa_{p,q} = B_{p,...

4

That's the Metric $k$-center problem.

answered May 16 '14 at 4:17

Thomas Kalinowski

2,82622 gold badges1515 silver badges2121 bronze badges

4

$\newcommand{\Ag}{\mathcal{A}_\gamma}$
Not a full answer, put probably a fruitful pointer:
In the discretization of infinite dimensional problems one faces (bi-)infinite matrices. There, the Jaffard algebra $\Ag$ of bi-infinte matrices (for some $\gamma>1$) is
$$
\Ag = \{A \ : \ |a_{k,l}|\lesssim (1+ |k-l|)^\gamma\}.
$$
It can be shown that the Jaffard ...

matrices na.numerical-analysis approximation-algorithms nonlinear-optimization numerical-linear-algebra

4

The question is stated informally, using the terms "queries" and "access".
Here is how I formally interpret it:
Take any $s$ and $t$ in $(0,1)$. Let $G_{s,t}$ be the set of all continuous strictly increasing functions $g\colon[0,1]\to[0,1]$ such that the set
$$E:=E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$
is nonempty. Do there ...

3

It depends on the model of computation you're using. If your memory slots can contain arbitrarily large integers (rather than single bits), and you can perform arithmetic operations in constant time, the answer is yes. Basically you use the following algorithm to step through the Farey sequence of the correct order:
https://en.wikipedia.org/wiki/...

answered Nov 29 '15 at 16:33

Adam P. Goucher

11.3k22 gold badges4646 silver badges8888 bronze badges

3

If the number and position of the knots are fixed, then the problem is a linear least squares problem for determining the coefficients of linear B-Splines (cf e.g http://en.wikipedia.org/wiki/B-spline); if the knot-positions also have to be determined, then the problem becomes non-linear, but is also studied in approximation theory.
This article seems to ...

3

Do you care more about the curve or the surfaces? Replacing the first function in your example by $100(x^2 + y^2 - 16)$ or $x^2-z^2+9$ gives the same curve but a different error function.
Also, consider the intersection of the cylinder $(x-11)^2+(y-11)^2=221$ and the plane $x+y-z=1.$ It is an ellipse and the portion $\mathit{C}$ in the positive octant goes ...

ag.algebraic-geometry polynomials approximation-theory real-algebraic-geometry approximation-algorithms

3

There is an easy $2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching $M$ can be found greedily. Initialize $M=\emptyset$. Add any edge $xy$ to $M$, and in $G -x-y$ search for another edge to add and recurse.
Let $m$ be the size of a minimum maximal matching. To show ...

3

You have to find a way to reduce the size of your simplicial complex. Some algorithms based e.g. on discrete Morse theory can do that fairly rapidly, but they don't have guarantees on the amount of size reduction. I don't think there exists faster algorithms for approximate Betti numbers in general, but I believe it can be done if your simplicial complex is "...

at.algebraic-topology gt.geometric-topology approximation-algorithms data-analysis persistent-homology

3

There is a way to speed-up Bourgain's embedding in case if the original metric space has low "intrinsic dimension". The resulting algorithm will have a theoretical runtime $O(CN\log^2(N))$, where $C$ is a constant depending only on "intrinsic dimension". And also will show speedups over the standard Bourgain's embedding varying between one and several orders ...

3

You can solve this problem via integer linear programming. Let binary decision variable $x_i$ indicate whether you can open door $i$, and let binary decision variable $y_j$ indicate whether you select key $j$. The problem is to maximize $\sum_{i=1}^N x_i$ subject to
\begin{align}
\sum_{j=1}^M y_j &= k \\
x_i &\le y_j &&\text{if door $i$ ...

2

I have recently computed a large table of rigorous values of the Stieltjes constants. Thanks to some coding by Jon Bober, the table can be browsed using a web interface on LMFDB.org (the L-functions and modular forms database):
http://beta.lmfdb.org/riemann/stieltjes/
For any $n \le 10^5$, the web interface allows printing $\gamma_n$ to at least 10000 ...

answered Oct 18 '13 at 14:39

Fredrik Johansson

1,66811 gold badge1212 silver badges1717 bronze badges

2

Your reference to eigenvalues suggests that you are minimizing $\sum_i P(x_i, y_i)^2$ subject to a constraint like $\sum_{a,b} P_{ab}^2=1$, where $P(x,y) = \sum_{a,b} P_{ab} x^a y^b$. Why not instead minimize $\sum_i P(x_i, y_i)^2$ subject to a linear constraint like $P_{00}=1$?
This is a standard approach when fitting a conic through a cloud of points (...

answered Dec 4 '15 at 16:45

David E Speyer

130k1111 gold badges339339 silver badges644644 bronze badges

2

Since you're using sage, I'd write a quick C or Cython function. Use the Arb library (I think this is already included in the latest release of sage) by computing the function in the naive way using the gamma function.
The benefit to doing so, is that the library uses "Ball" arithmetic and automatically finds rigorous error bounds for the computation.
...

2

The principles behind embedded Runge-Kutta-Methods apply:
You compute the integral over a subinterval with two methods of different order. You use the difference between the two results as an estimate for the local quadrature error of the less accurate formula.
In order to meet a global tolerance, you sum up these local errors. If the sum is above the ...

2

This is an extended comment. What exactly you are trying to minimize?
First version: given an algebraic curve with equation $F(x,y)=0$,
and two points on this curve $M,N$,
find the polynomials $p,q$ of degree at most $d$ such that
$(p(0),q(0))=M$, $(p(1),q(1))=N$, and
$$\max_{t\in[0,1]}|F(p(t),q(t))|$$
is minimal.
Some condition about two points is ...

answered May 1 '14 at 14:21

Alexandre Eremenko

70.4k66 gold badges202202 silver badges337337 bronze badges

2

Expanding on my comment ...
There's some material on bivariate approximation in Carl deBoor's book entitled "A Practical Guide to Splines".
Specifically, chapter XVII has results on approximation by tensor products and code to implement this. The code is also available in the matlab spline package.

2

You might find the idea of Companion matrix to be useful. The eigenvalues $\lambda$ of the companion matrix $C$ are equal to the roots of a polynomial and its eigenvectors $v$ are functions of the eigen-values and $v$ are linearly independent iff the eigenvalues(ie, roots) are distinct.
Now the question becomes that if only have noisy estimates of the ...

2

Since each row $r$ has a finite number of non-zero elements, say $N_r \subset \{1, 2, \dots\}$, you could use the Gillespie algorithm to simulate the continuous time Markov chain. A stationary distribution can then be approximated by the normalized occupancy times. If the matrix is irreducible, this will be the stationary distribution.
Here is an outline of ...

2

Yes, we do have "approximate complementary slackness" in the following sense.
Consider the standard (primal) linear programming problem:
max $c^T x$ s.t. $A x \le b$, $x \ge 0$
If $x^*$ and $y^*$ are primal and dual feasible solutions, we have
$$ c^T x^* \le y^* A x^* \le y^* b$$
with equality iff $x^*$ and $y^*$ are optimal.
Now let's say $x^*$ is ...

2

No, a fixed number of added vertices can change the John ellipsoid by an arbitrary amount when added to arbitrarily many already known vertices: consider a very thin regular n-gon prism centered about the origin. Now we can add two new vertices in a way that doesn't change the polyhedron much (near existing vertices, say), or we can add two new vertices ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

approximation-algorithms × 136algorithms × 50

graph-theory × 32

co.combinatorics × 25

computational-complexity × 22

na.numerical-analysis × 16

approximation-theory × 12

combinatorial-optimization × 11

linear-algebra × 8

nt.number-theory × 6

real-analysis × 6

linear-programming × 6

pr.probability × 5

matrices × 5

oc.optimization-and-control × 5

convex-polytopes × 4

computer-science × 4

np × 4

reference-request × 3

fa.functional-analysis × 3

mg.metric-geometry × 3

polynomials × 3

sequences-and-series × 3

integration × 3

graph-colorings × 3