Algorithm to find matching pairs in a list

Question

I will phrase the problem in the precise form that I want below:

Given: Two floating point lists N and D of the same length k (k is multiple of 2). It is known that for all i=0,...,k-1, there exists j != i such that D[j]*D[i] == N[i]*N[j]. (I'm using zero-based indexing)

Return: A (length k/2) list of pairs (i,j) such that D[j]*D[i] == N[i]*N[j]. The pairs returned may not be unique (any valid list of pairs is okay)

The application for this algorithm is to find reciprocal pairs of eigenvalues of a generalized palindromic eigenvalue problem. The equality condition is equivalent to N[i]/D[i] == D[j]/N[j], but also works when denominators are zero (which is a definite possibility). Degeneracies in the eigenvalue problem cause the pairs to be non-unique.

More generally, the algorithm is equivalent to:

Given: A list X of length k (k is multiple of 2). It is known that for all i=0,...,k-1, there exists j != i such that IsMatch(X[i],X[j]) returns true, where IsMatch is a boolean matching function which is guaranteed to return true for at least one j != i for all i.

Return: A (length k/2) list of pairs (i,j) such that IsMatch(i,j) == true for all pairs in the list. The pairs returned may not be unique (any valid list of pairs is okay)

Obviously, my first problem can be formulated in terms of the second with IsMatch(u,v) := { (u - 1/v) == 0 }. Now, due to limitations of floating point precision, there will never be exact equality, so I want the solution which minimizes the match error. In other words, assume that IsMatch(u,v) returns the value u - 1/v and I want the algorithm to return a list for which IsMatch returns the minimal set of errors. This is a combinatorial optimization problem. I was thinking I can first naively compute the match error between all possible pairs of indexes i and j, but then I would need to select the set of minimum errors, and I don't know how I would do that.

Clarification

The IsMatch function is reflexive (IsMatch(a,b) implies IsMatch(b,a)), but not transitive. It is, however, 3-transitive: IsMatch(a,b) && IsMatch(b,c) && IsMatch(c,d) implies IsMatch(a,d).

Addendum

This problem is apparently identically the minimum weight perfect matching problem in graph theory. However, in my case I know that there should be a "good" perfect matching, so the distribution of edge weights is not totally random. I feel that this information should be used somehow. The question now is if there is a good implementation to the min-weight-perfect-matching problem that uses my prior knowledge to arrive at a solution early in the search. I'm also open to pointers towards a simple implementation of any such algorithm.

Answer 1

I hope I got your problem.

Well, if IsMatch(i, j) and IsMatch(j, l) then IsMatch(i, l). More generally, the IsMatch relation is transitive, commutative and reflexive, ie. its an equivalence relation. The algorithm translates to which element appears the most times in the list (use IsMatch instead of =).

Answer 2

(If I understand the problem...) Here is one way to match each pair of products in the two lists.

1. Multiply each pair N and save it to a structure with the product, and the subscripts of the elements making up the product.
2. Multiply each pair D and save it to a second instance of the structure with the product, and the subscripts of the elements making up the product.
3. Sort both structions on the product.
4. Make a merge-type pass through both sorted structure arrays. Each time you find a product from one array that is close enough to the other, you can record the two subscripts from each sorted list for a match.
5. You can also use one sorted list for an ismatch function, doing a binary search on the product.

Answer 3

well。。Multiply each pair D and save it to a second instance of the structure with the product, and the subscripts of the elements making up the product.

Answer 4

I just asked my CS friend, and he came up with the algorithm below. He doesn't have an account here (and apparently unwilling to create one), but I think his answer is worth sharing.

// We will find the best match in the minimax sense; we will minimize
// the maximum matching error among all pairs. Alpha maintains a
// lower bound on the maximum matching error. We will raise Alpha until
// we find a solution. We assume MatchError returns an L_1 error.

// This first part finds the set of all possible alphas (which are
// the pairwise errors between all elements larger than maxi-min
// error.
Alpha = 0
For all i:
    min = Infinity
    For all j > i:
     AlphaSet.Insert(MatchError(i,j))
     if MatchError(i,j) < min
      min = MatchError(i,j)
    If min > Alpha
     Alpha = min

Remove all elements of AlphaSet smaller than Alpha

// This next part increases Alpha until we find a solution
While !AlphaSet.Empty()
    Alpha = AlphaSet.RemoveSmallest()
    sol = GetBoundedErrorSolution(Alpha)
    If sol != nil
     Return sol

// This is the definition of the helper function. It returns
// a solution with maximum matching error <= Alpha or nil if
// no such solution exists.
GetBoundedErrorSolution(Alpha) :=
    MaxAssignments = 0
    For all i:
     ValidAssignments[i] = empty set;
     For all j > i:
      if MatchError <= Alpha
       ValidAssignments[i].Insert(j)
       ValidAssignments[j].Insert(i)

     // ValidAssignments[i].Size() > 0 due to our choice of Alpha
     // in the outer loop

     If ValidAssignments[i].Size() > MaxAssignments
      MaxAssignments = ValidAssignments[i].Size()
    If MaxAssignments = 1
     return ValidAssignments
    Else
     G = graph(ValidAssignments)
     // G is an undirected graph whose vertices are all values of i
     // and edges between vertices if they have match error less
     // than or equal to Alpha
     If G has a perfect matching
      // Note that this part is NP-complete.
      Return the matching
     Else
      Return nil

It relies on being able to compute a perfect matching of a graph, which is NP-complete, but at least it is reduced to a known problem. It is expected that the solution be NP-complete, but this is OK since in practice the size of the given lists are quite small. I'll wait around for a better answer for a few days, or for someone to expand on how to find the perfect matching in a reasonable way.

Answer 5

You want to find j such that D(i)D(j) = N(i)N(j) {I assumed * is ordinary real multiplication}

assuming all N(i) are nonzero, let

Z(i) = D(i)/N(i).

Problem: find j, such that Z(i) = 1/Z(j).

Split set into positives and negatives and process separately.

take logs for clarity. z(i) = log Z(i).

Sort indirectly. Then in the sorted view you should have something like -5 -3 -1 +1 +3 +5, for example. Read off +/- pairs and that should give you the original indices.

Am I missing something, or is the problem easy?

Answer 6

Okay, I ended up using this ported Fortran code, where I simply specify the dense upper triangular distance matrix using:

complex_t num = N[i]*N[j] - D[i]*D[j];
complex_t den1 = N[j]*D[i];
complex_t den2 = N[i]*D[j];
if(std::abs(den1) < std::abs(den2)){
 costs[j*(j-1)/2+i] = std::abs(-num/den2);
}else if(std::abs(den1) == 0){
 costs[j*(j-1)/2+i] = std::sqrt(std::numeric_limits<double>::max());
}else{
 costs[j*(j-1)/2+i] = std::abs(num/den1);
}

This works great and is fast enough for my purposes.

Answer 7

You should be able to sort the (D[i],N[i]) pairs. You don't need to divide by zero -- you can just multiply out, as follows:

bool order(i,j) {
  float ni= N[i]; float di= D[i];
  if(di<0) { di*=-1; ni*=-1; }

  float nj= N[j]; float dj= D[j];
  if(dj<0) { dj*=-1; nj*=-1; }

  return ni*dj < nj*di;
}

Then, scan the sorted list to find two separation points: (N == D) and (N == -D); you can start matching reciprocal pairs from there, using:

abs(D[i]*D[j]-N[i]*N[j])<epsilon

as a validity check. Leave the (N == 0) and (D == 0) points for last; it doesn't matter whether you consider them negative or positive, as they will all match with each other.

edit: alternately, you could just handle (N==0) and (D==0) cases separately, removing them from the list. Then, you can use (N[i]/D[i]) to sort the rest of the indices. You still might want to start at 1.0 and -1.0, to make sure you can match near-zero cases with exactly-zero cases.

Answer 8

hey this is some thing new which i haven't come across and things i know about database are very few...but its very informative site which is helpful