Omega test

Omega test

The Omega test is a system written by William Pugh <pugh@cs.umd.edu> and others for performing symbolic manipulations of conjunctions of linear constraints over integer variables. The Omega test dependence analyser is a system built on top of the Omega test to analyse array data dependences.

Version 3.2.2 includes a fortran to tiny translator, a Tiny interpreter(?) and analysis tools.

ftp://ftp.cs.umd.edu/pub/omega. E-mail: <omega@cs.umd.edu>.
Mentioned in ?
References in periodicals archive ?
Our experiments that suggest that, for almost all programs, the average time required by the Omega test to determine the direction vectors for an array pair is less than 500 [unkeyable]secs on a 12-MIPS workstation.
Conceptually, the Omega test combines new methods for eliminating equality constraints with an extension of Fourier-Motzkin variable elimination to integer programming.
Integer programming is a NP-Complete problem, and the Omega test has exponential worst-case time complexity.
Later we will show how the Omega test can be modified to project integer programming problems onto a subset of the variables, rather than just deciding them.
The Omega test determines whether there is an integer solution to an arbitrary set of linear equalities and inequalities, referred to as a problem.
Also, although many steps are performed in this process, our implementation of the Omega test takes only 4.
Worse nightmares are possible: on problems with only two variables and three constraints, the Omega test can take time proportional to the absolute value of the coefficients.
A decision on better methods for dealing with Omega test nightmares will have to wait until more experience is gained about the type of nightmares that occur in practice.
In implementing the Omega test we used several algorithmic ideas and tricks that substantially improved our running time.
Omega Tests are those scripted and unscripted, supervised and un-supervised, demonstrations of systems operation in the field.
An Omega strategy broadens the responsibility as Omega Tests are funded through a myriad of single and combined sources, including component commanders; training and doctrine commands; research, logistics, and engineering activities; intelligence agencies; programs; and other Service acquisition agents.
OTAs plan, manage, and oversee Omega Tests as well as assess capability in the field, working with the users to vet future capabilities, upgrades, or changes to doctrine and CONOPS.