Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Vector Union
Posted:
Apr 19, 2000 2:53 AM


The problem of finding a function to return the union of a list of nvectors 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 notsoslow 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 nvectors*. 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) 3892872



