A Covering Design c(v,k,t,m,b) is a pair (V,B), where V is a set of v elements (called points) and B is a collection of b k-subsets of V (called blocks) such that every m-subset of V intersects at least one member of B in at least t points. It is required that v >= k >= t and v >= m >= t. Given some parameters of a design and some subsets, how can you determine fast the number of Covered/Uncoverd blocks within these parameters? I'm looking for an algorithm or pseudocode to count the number of blocks that are covered/uncovered, with a method other than brute force. Some examples of partially covered designs below: Example #1, Parameters: v=12 k=5 t=4 m=6 b=9 1 3 5 6 12 1 4 7 9 12 1 8 9 10 11 2 3 4 7 8 2 3 8 9 12 2 4 5 6 9 2 7 10 11 12 3 4 5 10 11 5 6 7 8 10 The above design covers 770 blocks of the possible 924. It leaves uncovered 154 blocks. My question again is as of methods/algorithms to count the number of covered/uncoverd blocks as fast as possible. Example #2, Parameters: v=18 k=7 t=4 m=7 b=11 1 2 3 4 9 14 18 1 2 3 4 11 12 13 1 2 5 6 7 8 9 1 2 8 15 16 17 18 1 7 8 10 11 15 16 2 10 12 13 14 15 16 3 4 5 6 7 14 17 3 4 5 6 8 10 18 3 4 9 10 15 16 17 5 6 7 11 12 13 18 8 9 11 12 13 14 17 Covered blocks=31,692 of the possible 31,824. Uncovred blocks=132 Example #3, Parameters: v=15 k=6 t=3 m=4 b=14 1 2 3 4 5 6 1 2 3 7 10 13 1 3 6 8 12 13 1 4 7 8 10 14 1 5 9 12 13 14 1 6 7 9 11 13 2 4 10 11 12 15 2 5 6 7 12 14 2 8 9 11 14 15 3 4 7 9 12 15 3 5 10 11 14 15 4 5 7 8 11 13 4 6 9 13 14 15 5 6 8 9 10 15 Covered blocks=1363 of the possible 1365. Uncovred blocks=2 Your ideas or comments are welcome. ==== > >> Dear Group, >> I`m trying to calculate a 2D fourier transform >> (2DFFT) of >> a 2d exponential decay. Upon comparisions with a lorentzian form >> ( i compare the normalized values of the real and the imaginary >> parts seperately) i see that with my best efforts i can achieve >> an accuracy of only 10^(-3). Even this is possible only if go to >> a totally unacceptable time step (In order to get a reasonable >> resolution in the frequency domain i would need to do a 8192x8192 >> FFT calculation). >> I`m unable to locate where the error is coming from. >> I >> don`t think my problem is related to zero padding as i can choose >> a decay const which ensure that the value goes to zero within the >> interval. I would be really grateful to any comments and pointers >> as i`m really stuck. (i need an accuracy of at least 10^(-5) to >> proceed). >> >> Ravi > > Have you remembered to halve the t=0 input datum? -- ==== > On Sat, 10 Jan > > > > Have you remembered to halve the t=0 input datum? I`m sorry i don`t understand. why is this necessary? Ravi ==== >> On Sat, 10 Jan > >> >> >> Have you remembered to halve the t=0 input datum? > > I`m sorry i don`t understand. why is this necessary? > > Ravi > Think of the finite fft as an approximation to the integral fourier transform. If you make a trapezoidal approximation to the integral, the first and last points must have weight 0.5 relative to the internal points. For a signal that decays to 0, the last point doesn't matter, but the first one does. -- ==== Download beta 1 - www.master-graph.com/mgraph20b1.exe (only 477KB). All who will help me to improve this program will get a free registration key. You can do the following: -find bugs -feedback about you impression by the program -advice me to change or add some new features -translate it to the other language (see www.master-graph.com/instructions/interface.html) Feel free to contact with me - roman@master-graph.com Sincerely, Roman. ==== Dear all, Convex optimization seems hot today... anybody can tell me what is the relationship and difference between linear/nonlinear, discrete, and convex optimization? -Walala ==== I haven't looked into ASM for years, so I can only repeat what I have > read elsewhere: that current-day compilers are quite good at generating > decent machine code. That mantra has enough wiggle room in it to get out of anything. Define decent. Decent to run MS-Word? > For whatever definition of quite good. (You might > want to direct this kind of question to comp.compilers.) I did actually. No surprises there. > Anyway, optimization isn't just generating good ASM code, it's also > stuff like loop unrolling, common subexpression elimination, etc. > C and C++ are notoriously hard to optimize this, since it's often very > difficult to trace which pointer may refer to what array. Fortran > compilers have a far easier job since Fortran programs don't use > pointers, they use indexes (at least that used to be true for older > Fortran code, and I'm pretty sure that all the numeric libraries are > still written in that style). Yes, some languages have more burdens than others. The simpler the programming model, the easier to optimize. > The DEC Alpha compiler was the exception. Anyways > this is imperative stuff, for mainstream languages like C and C++, so pretty > much the natural fit to the task of optimizing the CPU instruction stream. Not really. I suppose I didn't state my point clearly. CPU instruction streams are fundamentally imperative. That is my point. I don't care about C or C++, that's a sideshow. The point is, functional programming is inherently a layer of complication on top of the imperative machine architecture. > Still, since functional > languages tend to have a far simpler semantics than imperative ones, > it's less work to get the compiler right, so there's more time for doing > a good code generation backend *g*) This is all theory. Look at what happens in industrial practice. Nothing much. -- Brandon Van Every Seattle, WA 20% of the world is real. 80% is gobbledygook we make up inside our own heads. ==== > >> I haven't looked into ASM for years, so I can only repeat what I >> have read elsewhere: that current-day compilers are quite good at >> generating decent machine code. > > That mantra has enough wiggle room in it to get out of anything. > Define decent. Decent to run MS-Word? Decent in the sense that writing faster code in ASM requires expert knowledge (i.e. real experience, as opposed to just knowing the instruction set, register structure, and memory model). >> Anyway, optimization isn't just generating good ASM code, it's also >> stuff like loop unrolling, common subexpression elimination, etc. >> C and C++ are notoriously hard to optimize this, since it's often >> very difficult to trace which pointer may refer to what array. >> Fortran compilers have a far easier job since Fortran programs >> don't use pointers, they use indexes (at least that used to be true >> for older Fortran code, and I'm pretty sure that all the numeric >> libraries are still written in that style). > > Yes, some languages have more burdens than others. The simpler the > programming model, the easier to optimize. Then you should like functional languages :-) > The DEC Alpha compiler was the exception. Anyways this is > imperative stuff, for mainstream languages like C and C++, so > pretty much the natural fit to the task of optimizing the CPU > instruction stream. > >> Not really. > > I suppose I didn't state my point clearly. CPU instruction streams > are fundamentally imperative. That is my point. Well... er... no, your point was clear enough. My point, however, is that modern languages are quite far from CPUs in other ways. The hoops that a compiler is expected to jump through are many, and having to translate the stuff from functional to imperative is just another hoop (and a quite easy one: the techniques aren't very difficult - actually OCaml, the language and implementation that's commonly considered to be the fastest functional language around, doesn't use many compiler tricks, just a solid backend). And before you say OCaml may be the fastest functional language around, but it doesn't beat C: OCaml actually has beaten C in several ICFP contests. (See below for more on ICFP.) > The point is, functional programming is inherently a layer of > complication on top of the imperative machine architecture. It's a step further away, but it's quite far from being a complication! Functional languages have a far, far simpler semantics than their imperative counterparts. (That's one of the reasons why optimizing them is easier.) >> Still, since functional languages tend to have a far simpler >> semantics than imperative ones, it's less work to get the compiler >> right, so there's more time for doing a good code generation >> backend *g*) > > This is all theory. Look at what happens in industrial practice. > Nothing much. Ever looked at the ICFP contest results? 36 hours time, same task for everybody, and everybody gets to choose his favorite language. Most contests ended up with OCaml winning or among the first three places. More interesting: Participants are encouraged to publish a log of their activities. Teams using an imperative language usually work on the base algorithm until the very last minute. Teams using a functional language usually have a working program in very little time (I have seen everything between 6 and 24 hours), after which they start implementing optimizations. I don't think that this is theory. Jo -- Currently looking for a new job. X-Received: (from approve@localhost) by support1.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) id i08K3Bc26460; ==== Dear reader, Based on the arithmetic of computers, could someone please tell me which of the following two iterative functions is more eficient? : ( Both yield the fifth root of any positive number P, that is: P^(1/5) ) First one: (4xP^2 + 17Px^6 + 4x^11) / (2P^2 + 16Px^5 + 7x^10) (Householder's iterative function, fourth order convergence) Second one: (10xP^2 + 15Px^6)/(6P^2 + 18Px^5 + x^10) My vote is for the second one. This is not homework. Many thanks for your comments. Domingo Gomez X-Received: (from approve@localhost) by support1.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) id i0AD3W216557; ==== can anybody give me any guidelines to using the chaboche material model in ansys. X-Received: (from approve@localhost) by support1.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) id i0AKr8H16701; ==== I have 2 groups of data that come in several continuous batches of equal size. I wish to compute their covariance. Certainly I can view all batches in each group as one piece of data. Therefore computing their covariance is as usual. However I do not want to do it that way because each batch may have different mean and I do not wish all batches to carry one mean value (for some reasons.) Instead, I calculate covariance for each batch using, BATCH_COV(A,B) = 1/M * SUM_i {(A_i - mean(A)) * (B_i - mean(B))} where M = number of elements in a batch and i = element index. Then calculate the complete covariance as COV(X,Y) = 1/N * SUM_j {BATCH_COV(X^j,Y^j)} where N = number of batches and j = batch index. Is this mathematically correct? Please advice. ==== You might consider that: d(log(x+y))/dx = d(log(x+y))/dy = 1/(x+y) It's unclear what kind of optimization problem you want to solve. Without any more information than that, log(x+y) clearly doesn't have any local minimum.