Approach to effective implementation of numerical algorithms

The problem of effective implementation of numerical algorithms is actual. The paper proposes a solution to this problem. The solution uses the author’s concept of a 𝑄-determinant. In the paper, we describe the notions of the concept of a 𝑄-determinant used for research. These are the following notions. An algorithmic problem has the form ¯𝑦 = 𝐹(𝑁,𝐵), where 𝑁 = {𝑛1, . . . ,𝑛𝑘} is the set of parameters of the problem dimension or 𝑁 is the empty set, 𝐵 is the set of input data, ¯𝑦 = {𝑦1, . . . ,𝑦𝑚} is the set of output data. Here 𝑛𝑖 (𝑖 ∈ {1, . . . ,𝑘}) is any positive integer. If 𝑁 = {𝑛1, . . . ,𝑛𝑘}, then by ¯𝑁 = {¯𝑛1, . . . ,¯𝑛𝑘} we denote a set of 𝑘 positive integers, where ¯𝑛𝑖 is some given value of the parameter 𝑛𝑖 for each 𝑖 ∈ {1, . . . ,𝑘}. We denote the set of all possible 𝑘-tuples ¯ 𝑁 by { ¯ 𝑁 }. An algorithm for solving an algorithmic problem is denoted by 𝒜, and the set of operations used by algorithm 𝒜 is denoted by 𝑄. An expression over 𝐵 and 𝑄 is a term in the standard sense of mathematical logic. A chain of length 𝑛 is the result of applying some associative operation from 𝑄 to 𝑛 expressions. If 𝑁 = ∅, then any expression 𝑤 over 𝐵 and 𝑄 is an unconditional 𝑄-term. If 𝑁 ̸= ∅ and 𝑉 is the set of all expressions over 𝐵 and 𝑄, then any mapping 𝑤 : {︀ ¯𝑁 }︀ → 𝑉 ∪∅ is also called an unconditional 𝑄-term. 𝑤( ¯ 𝑁 ) = ∅ means that the value of 𝑤( ¯ 𝑁 ) is undefined. If 𝑁 = ∅ and the expression 𝑤 over 𝐵 and 𝑄 has a value of logical type under any interpretation of the variables 𝐵, then we call the unconditional 𝑄-term 𝑤 an unconditional logical 𝑄-term. Let 𝑁 ̸= ∅ and 𝑤 be an unconditional 𝑄-term. Suppose also that the expression 𝑤( ¯ 𝑁 ) for each ¯ 𝑁 ∈ { ¯ 𝑁 } has a value of logical type under any interpretation of the variables 𝐵. In this case, we call the unconditional 𝑄-term 𝑤 an unconditional logical 𝑄-term. Suppose that 𝑢1, . . . ,𝑢𝑙 are unconditional logical 𝑄-terms, 𝑤1, . . . ,𝑤𝑙 are unconditional 𝑄-terms. Then the set 𝑙 of pairs (̂︀𝑢, ̂︀𝑤) = {(𝑢𝑖,𝑤𝑖)}𝑖∈{1,...,𝑙} is a conditional 𝑄-term of length 𝑙. Let (̂︀𝑢, ̂︀𝑤) = {(𝑢𝑖,𝑤𝑖)}𝑖=1,2,... be a countable set of pairs of unconditional 𝑄-terms. Suppose that {(𝑢𝑖,𝑤𝑖)}𝑖∈{1,...,𝑙} is a conditional 𝑄-term of length 𝑙 for any 𝑙 < ∞. Then we call (̂︀𝑢, ̂︀𝑤) a conditional infinite 𝑄-term. 𝑄-terms can be calculated. Suppose that algorithm 𝒜 consists in finding for each 𝑖 ∈ {1, . . . ,𝑚} the value 𝑦𝑖 by computing the value of the 𝑄-term 𝑓𝑖. Then the set of 𝑄-terms {𝑓𝑖 | 𝑖 ∈ {1, . . . ,𝑚}} we call the 𝑄-determinant of the algorithm 𝒜. Moreover, we call the system of equations {𝑦𝑖 = 𝑓𝑖 | 𝑖 ∈ {1, . . . ,𝑚}} a representation of the algorithm 𝒜 in the form of a 𝑄-determinant. The process of computing 𝑄-terms {𝑓𝑖 | 𝑖 ∈ {1, . . . ,𝑚}} of algorithm 𝒜 is called an implementation of algorithm 𝒜. An implementation of algorithm 𝒜 is called parallel if there are operations of the algorithm that are executed simultaneously. An implementation of algorithm 𝒜 is called 𝑄-effective if 𝑄-terms {𝑓𝑖 | 𝑖 ∈ {1, . . . ,𝑚}} are computed simultaneously, operations are executed as they are ready, and chain operations are computed using the doubling scheme. A 𝑄-effective implementation uses the entire parallelism resource of the algorithm. The concepts of height and width of an algorithm characterize the parallelism resource of the algorithm. An implementation of the algorithm 𝒜 is called realizable if it is such that a finite number of operations must be executed simultaneously. There are algorithms such that the 𝑄-effective implementation is not realizable. We can use the 𝑄-determinant of a numerical algorithm for design parallel programs implementing the algorithm, including effective programs. On the base of this idea, the author has developed a method for designing effective programs. In this paper, we describe the proposed method. The method involves the following steps: construction of the 𝑄-determinant of the algorithm, description of the 𝑄-effective implementation of the algorithm, development of a program for an realizable 𝑄-effective implementation of the algorithm. We call 𝑄-effective programs developed using the effective program design method. Therefore, we can also call this method the method of designing 𝑄-effective programs. Note that 𝑄-effective programs use the parallelism resource of algorithms completely. In the paper, we provide an overview of the numerical algorithms for which 𝑄-effective programs have been developed. We also describe the features of applying the design method of 𝑄-effective programs to algorithms. Note that we are considering algorithms that solve various algorithmic problems and have a different structure of 𝑄-determinants. In addition, we present the following results of a study of 𝑄-effective programs. 1) We introduce the concept of the computing infrastructure of the program.