The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Inactive » comp.soft-sys.math.mathematica

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Russell Towle

Posts: 70
Registered: 12/3/04
Vector Union
Posted: Apr 19, 2000 2:53 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic 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
Read Vector Union
Russell Towle
Read Re: Vector Union
Jens-Peer Kuska

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

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