Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Vector Union
Replies: 1   Last Post: Apr 20, 2000 5:59 PM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Russell Towle Posts: 70 Registered: 12/3/04
Vector Union
Posted: Apr 19, 2000 2:53 AM
 Plain Text Reply

The problem of finding a function to return the union of a list of
n-vectors which is at once *fast* and yet *unfailing* has beguiled me for
several years. I contrived a slow but unfailing 'vunion' function about
five years ago; made a not-so-slow and unfailing version a year ago; and
then found it to occasionally fail when Chop was applied to the vectors
without a second argument.

I posed a programming challenge to the Group a few days ago: make a fast
and unfailing vector union function. David Park and Michael Trott were kind
enough to respond, for which I thank them very much. Around a year around
Martin Kraus also supplied a vector union function.

Good solutions seem to hinge upon *sorting the list of n-vectors*.
Searching the internet, I find that sorting a list of vectors seems to be a
classic problem in computer science. This is where Chop comes into play: to
compare one vector to another, when the components are machine precision,
is easier when very small numbers with opposite signs are Chopped to zero.

My function, slow but sure:

vunion[v_] :=
Union[Chop[v, .000001],
SameTest -> (Sign[#1] == Sign[#2] &&
Chop[#1 - #2, .000001] == Table[0, {Length[v[[1]]]}] & )]

David Park appealed to an "UnorderUnion" function devised by Carl Woll,
which works well on lists with integer and symbolic components. Park uses
Round to put the machine numbers into a form acceptable to UnorderUnion.
The implications of using Round worry me, but Park's method has not failed
yet, given inputs which made most other methods fail. His function is
around twenty times faster than mine. Thanks David!!

(*modified Woll*)
OrderedUnion2[li_] :=
Block[{i}, i[n_] := (i[n] = Null; n);
i /@ li]

vunion2[v_] :=
Block[{accuracylist, v2},
accuracylist = OrderedUnion2[Round[10^5*(v2 = Sort[Chop[v, .000001]])]];
Do[If[accuracylist[[i]] === Null, v2[[i]] = Null], {i, Length[v2]}];
v2 /. Null -> Sequence[]]

Russell Towle
Box 141
Dutch Flat, CA 95714
(530) 389-2872

Date Subject Author
4/19/00 Russell Towle
4/20/00 Jens-Peer Kuska

© The Math Forum at NCTM 1994-2018. All Rights Reserved.