hardmath
  • Member for 10 years
  • Last seen this week
Fitting one set of points to another by a rigid motion
Accepted answer
14 votes

Inge Söderkvist (2009) has a nice write-up of solving the Rigid Body Movement Problem by singular value decomposition (SVD). Suppose we are given 3D points $\{x_1,\ldots,x_n\}$ that after ...

View answer
How can I determine the initial values of pseudo-random number generator if the sequence is given?
Accepted answer
11 votes

See the paper How to crack a Linear Congruential Generator, Haldir ("Reverse Engineering Team", Dec. 2004): In this paper I will present a method which will solve all values of the LCG including ...

View answer
How to approximate the condition number of a large matrix?
Accepted answer
11 votes

MATLAB has a couple of "exact" functions for this, cond and rcond, with the latter returning a reciprocal of the condition number. Matlab approximate function condest is more fully described below. ...

View answer
Why can't Householder reflections diagonalize a matrix?
11 votes

As the Comments to other Answers clarify, the real issue here is not a shortcoming of Householder matrices but rather a question as to why iterative rather than direct ("closed-form") methods are used ...

View answer
Open source implementation of rational approximation to a function
10 votes

Doing one-off best rational approximations can often be accomplished by "manual" iterations of the Remez algorithm: interpolate a rational approximation with (relative or absolute) alternating sign ...

View answer
What is the most efficient way to diagonalize small matrices?
8 votes

Let me add a few remarks explaining why there is no better method for "small" matrices in the range described (order 4 to 64) than the usual approach: tridiagonalize the Hermitian matrix with a ...

View answer
Analyzing Numerical Error in C++ Function
8 votes

A nice portable and open source library for arbitrary precision floating point arithmetic (and much else) is Victor Shoup's NTL, which is available in C++ source form. At a lower level is the GNU ...

View answer
How to use polylogarithm function in c++?
7 votes

There's a GPL'd C library, ANANT - Algorithms in Analytic Number Theory by Linas Vepstas, which includes multiprecision implementation of the polylogarithm, building on GMP. From its README file: ...

View answer
Machine epsilon does not limit relative rounding error for denormals. Is this a problem?
Accepted answer
7 votes

Back in the era of Intel 387 math coprocessors I had to maintain an interrupt handler for floating point exceptions. Apart from that, I agree that pretty much everyone ignores denormals (or ...

View answer
Compiled c++ code runs much faster with double than float. Explanation?
Accepted answer
6 votes

I have looked at your simple code example, and my suspicion is that what you observe in loss of speed is due to the C-heritage requirement that right-hand side expressions be evaluated using ...

View answer
Condition number of $X^{T}AX$
6 votes

Let's show that we cannot bound the condition number of $X^T A X$ by using only the condition number of $A$ and the norm of $X$. Let $A=I$, so its condition number is exactly $1$. Let $X$ consist of ...

View answer
How to avoid overflow error in program that computes product of two numbers, such that when one is big enough to cause overflow, other is $0$?
Accepted answer
6 votes

Initially the Question focused on a product computation, f(x)*g(x), where one factor is very small and the other is very large (perhaps large enough to cause overflow in floating point representation)....

View answer
Selecting most scattered points from a set of points
6 votes

With a very large number $N$ of points and a small subset $M$ to be chosen, it may be helpful to consider what is known about continuous versions of the problem in two-dimensions. L. Fejes Tóth ("On ...

View answer
How to integrate numerically over a radial domain
Accepted answer
6 votes

Since the outer integral $\int_0^{2\pi} F(\theta) d\theta$ has a periodic integrand, a trapezoidal rule should work nicely, picking up extra accuracy when $F(\theta)$ is smooth. For the inner ...

View answer
Bad scaling versus collinearity
Accepted answer
6 votes

Yes, that's what it means. This is usually illustrated with $A$ a diagonal matrix having both large and small entries. Clearly such a matrix can be accurately inverted, but a simple measure of ...

View answer
Simplifying some operations on Gram matrices
Accepted answer
6 votes

In the restated problem both $X$ and $Y$ have rank at most $k \ll n$, and the same is true of Gram matrices $A$ and $B$. Also $C=(X+Y)(X+Y)^T$ will have rank at most $k$. The goal of forming $C$ ...

View answer
What is the best high performance computing platform for engineering simulations?
6 votes

Linux takes all ten of the top 10 spots in petaflops/supercomputing, but the operating system is perhaps not the only aspect you should focus on. Most developers will never get "time" on the highest ...

View answer
Minimizing the Sum of Absolute Deviation ($ {L}_{1} $ Distance)
6 votes

The explicit solution in terms of the median is correct, but in response to a comment by mayenew, here's another approach. It is well-known that $\ell^1$ minimization problems generally, and the ...

View answer
How does Mathematica compute real and complex solutions to single, non-polynomial equations?
5 votes

As the other Answer already touches on the possibility of a symbolic root-solver being applied to this particular equation (by transforming into a polynomial form, albeit of degree $\ge 5$), I'll make ...

View answer
Maximum translation distance between piecewise functions that satisfy a condition
Accepted answer
5 votes

As a general rule in developing and testing numerical software, I try to eliminate as many parameters as possible. I'm sure it has occurred to you that the distance $d$ and "floor" $z$ are scalable ...

View answer
Testing if two 12x12 matrices have the same determinant
5 votes

Without some information about the construction of these $12\times 12$ positive definite real symmetric matrices, the suggestions to be made are of necessity fairly limited. I downloaded the ...

View answer
computing the determinant of a dense nonsymmetric 100x100 matrix having very big and very small eigenvalues
5 votes

The computation of integer-valued matrix determinants has been a subject of considerable research. Using exact arithmetic the Smith normal form can be computed, and from this diagonal form the ...

View answer
Algorithms for community detection for bipartite graphs?
5 votes

The phrase "community detection" is loosely defined as partitioning the vertices of a graph into "communities" such that each has members more densely linked to one another than to members of other "...

View answer
Problems Implementing the Remez Algorithm
4 votes

Let's use the example (approximate the square root function on $[0.25,1.0]$ with a quartic polynomial) to step through your calculations. I suspect that the code is going to work with only modest ...

View answer
Optimization of prime factorization in C
4 votes

Since Doug has pointed out the need for a bigger integer datatype to do the problem you want to tackle, let's talk about the logic of your program and improvements. Your approach is (A) input alpha ...

View answer
Solving system of linear equations with cyclic tridiagonal matrix
Accepted answer
4 votes

It is not difficult to determine the complexity of a straightforward elimination/reduction to upper triangular form. Note that the initial matrix: $$ \begin{bmatrix} a_1&b_1&0&\cdots&...

View answer
For software submitted to ACM TOMS, how does the ACM software license agreement interact with other licenses?
Accepted answer
4 votes

Normally the author of a work can license it under more than one of the open source licenses you mention (so called dual licensing). However there seems to be an issue with doing so under the ...

View answer
How to solve a small least-squares problem
4 votes

I'd guess a QR decomposition is better than solving the normal equations and faster than SVD. There are some class notes that compare the three approaches. Also: The QR decomposition for least-...

View answer
SVD for finding the largest eigenvalue of a 50x50 matrix -- am I wasting significant amounts of time?
4 votes

For a positive semi-definite matrix such as $A = XX^T$ it may be worth the effort to accelerate convergence with a spectrum shift. That is, a suitable scalar $\mu$ is chosen and the power method is ...

View answer
What equation should I fit this set of data points to?
3 votes

An assortment of curves for fitting chemistry examples is presented in these Colby College class notes. Of particular application is the sigmoid response curve with variable "slope" for the central ...

View answer