Queueing Networks

Acquisition of Stability in Queueing Networks – A Survey

By

Rana Sohail

MSCS (Networking), MIT

Abstract— Today is the era of high-speed networking where everyone wanted to be connected immediately without any delay. The immediate connection is not possible because of the increased number of customers trying to be connected at once. Resultantly a waiting situation is created which is resolved by making a queue where everybody gets the turn. The theory of queueing is very helpful in this regard where the model is constructed and bounded by prescribed scheduling policies. These policies are made keeping in view the network environment. The network is connected through a single or multiple queues upon which everybody has to be dependent. The queueing networks (QN) are stable till the time not overcrowded, but once overloaded the stability might be outclassed. The stability of the QN is related to the finite number of customers and the policies of their scheduling. There are a number of ways through which scheduling could be done to acquire stability in QN.

In this paper, the scheduling techniques, a number of challenges, and reasons for un-stability are discussed. Furthermore, remedial measures will be suggested to overcome the highlighted issues.

Keywords— Queueing Networks, stability, customers, scheduling policies

I. INTRODUCTION

The concept of queueing network is based upon the queueing theory. The theory is about a study that is mathematical in nature and deals with the waiting queues. A model is constructed which calculates the length of a queue and waiting time of each component in it. The model also follows a prescribed schedule through the components or customers are getting in and out of the queue. The scheduling is based on certain factors or policies which are dependent upon time, priority, or nature of the job of the waiting customers. At times queues follow the policies like First Come First Served (FCFS) as in [1] or First in First out (FIFO) as in [2], Last come First Served (LCFS) or Last in First out (LIFO), Shortest Job First as in [3], Processor Sharing (PS), Infinite Serves (IS), etc. 

    When the queues are connected in a network where customers are getting service at one place or node and moving to another node then such a system is known as queueing network. These networks are stable till the time there is a traffic load within a given parameter but once any of the parameters is overruled then the system will be unstable. This paper is organized to highlight the fundamentals of QN and stability with challenges in general and techniques of scheduling and acquiring of stability in particular. The available solutions will also be mentioned and the best among will be declared.
    The paper is organized into sections. In section II, QN basics are described. Section III deals with scheduling policies and performance parameters. In section IV, stability and its related challenges faced by QN are highlighted along with a proposed solution. In section V, the discussion will be concluded.

II. BASICS OF QUEUEING NETWORKS

    The network which deals with multiple queues is handled by a model known as Queueing Network Model (QNM) and it belongs to the Jackson Networks. There are a number of service stations that are inter-connected through the directed paths and the customers move around. The customers also are known as jobs get service at one station, move ahead, line up in another queue for another service from another station. These service stations hold a number of services required by the customers as in [4]. Figure 1 shows the QNM as under:-

A.    Types of QN

There are three categories of QN which can be classified as under:-

    1) Closed Queueing Network (CQN): In this sort of QN there is a close circuit in which no arrival or departure is possible. The population of customers in the network is constant and keeps on circulating as in [5]. The customers may visit any queue twice as per requirement.  CQN models are good for analyzing those networks which deal with flow controls of windows and scheduling of CPU jobs as in [6]. Figure 2 depicts the CQN in detail as follows:-

    2) Open Queueing Network (OQN): In this sort of QN the customers arrive in the network from an external source and visit the number of queues, may repeat some queues as well, and depart the network after getting desired information. The customers’ numbers are not constant but a number of arrivals are always equal to the number of departures. There can be a described pattern of route following by the customers or maybe in an acyclic fashion. OQN models are good for packet switching (PS) and circuit switching (CS) data networks analysis as in [6]. Figure 3 depicts the OQN in detail as follows:-

3) Semi-open Queueing Network (SQN): This sort of QN holds the properties of both CQN and OQN. The OQN keep all the function less the customers' numbers are limited to finite jobs. In case of reaching the limit, the arrivals from external resources will be blocked, and once the job leaves the network the blocking of new arrivals will be over. So once the network is blocked then it behaves like CQN otherwise OQN as in [7].

B.    Types of Customers

Although all customer is taken as alike but according to their categorization, they seem different from each other. The difference is measured in terms of the required service timing by them and the probability of their routing in the network as in [8]. Following are types of customers:-

1) Chains: Customers having the same nature of jobs are grouped in a chain where the jobs are categorized permanently. Once this categorization of the job is done then one job of one chain can’t move or switch to the other chain. This is customers’ permanent categorization where a customer has to stay in a chain whole the time till departure.

2) Classes: The jobs of customers go through different phases like loading of a program and then its execution are two different phases. These phases are classified as classes and there may be many classes. The main fact is that these classes are within a specified chain. This is a customers’ temporary classification where a customer may switch within classes but in the same chain.

   3) Multiple Class Single Chain: This is a QN wherein a single chain there is a number of classes as in [9]. Figure 4 shows the concept where Chain 1 is an OQN which is formed by one class and chain 2 is CQN which is formed by one class as illustrated below:-

   4) Multiple Class Multiple Chain: This is a QN wherein multiple chains there is a number of classes as in [10]. Figure 5 shows the concept where Chain 1 is an OQN which is formed by classes 1 and 3 and chain 2 is CQN which is formed by class 2 as illustrated below:-

III.      POLICIES AND PERFORMANCE

In this section two important aspect are highlighted; the scheduling policies of QNs and certainly adopted parameters through which better performance is achieved. Following are the details:- 

A.    Scheduling Policies of QNs

There are a number of different policies that are adopted for QNs. Their details are under:-

1) First in First out (FIFO): It is also known as First Come First Served (FCFS). A buffer or queue is organized where the customers keep on coming and line up in a waiting lane. They are served according to their turn and after getting the required service from the server they keep on leaving the queue. The one who comes first is served first and the second one next and so on as in [11]. 

2) Last in First out (LIFO): A stack is organized where the customers keep on coming and stacking up. There are two operations namely Push and Pop through which the customers keep on getting in and out of the stack. Push adds the customers in the stack whereas pop removes them. The one who comes last is served first and the second last one next and so on as in [12].

3) Shortest Job First (SJF): It is a scheduling policy where that customer is selected whose job has the smallest time of execution. It is quite helpful that smaller time-consuming customers are moving frequently. But at times customers with a longer time may keep on waiting for their turn and could not get a turn because less time requiring customers to keep on coming. It creates process starvation. It is only useful where the aging technique is used for estimating the time of the job’s execution as in [13]. 

4) Processor Sharing (PS): It is a policy where the services are available to all the customers simultaneously. All the jobs are getting an equal share from the servers. In such a case there is no customer who has to wait for the turn, therefore, there are no queues as in [14].

5) Infinite Server (IS): In this scheduling policy when the customers enter the network they receive the serves right from the outset at rate 1. So there is a number of servers in the network which are unoccupied and their services are available all the time as in [15].

6) Random Selection for Service (RSS): In this, the customers are selected randomly without taking into care of their arrival or waiting time, etc.

B.    QN Performance Parameters

Once the performance of QN is to be judged then there is a need to check out certain parameters of QN. The parameters are related to the arrivals or inputs and departures or outputs of the QN. Like inputs include the number of stations, some scheduling discipline with service time distribution, population (CQN) or inter-arrival time (OQN) etc. Whereas outputs include the length of queues, response time, throughput, utilization, etc. as in [16]. Irrespective of input or out parameters, these are highlighted as under:-

• Average service time spent at a station for a customer.
• External arrival time in OQN only at which customers are arriving at the network from an external source.
• Routing probability of customers from one station to another.
• Throughput or completed services by the stations.
• Average the response time taken by customers at any station.
• Average waiting time taken by customers at any station.
• Average queue length of any station holding customers for waiting or serving.
• Average the waiting line length of customers waiting to be served excluding those who are under processing service.
• Utilization of any station in terms of time.
• Queue length distribution among customers at stations.

IV.  STABILITY AND THEIR RELATED  ISSUES

The QN is expected to be stable all the time which is not possible due to certain factors that are elaborated in the subsequent paragraphs. There are a number of related issues faced by the QN as well which are also highlighted within the stability scenario.

A.    Stability of QN

The stability of QN depends upon certain stationary distribution factors like disciplines, non-exponential inter-arrival and service times. The invariant distribution is determined explicitly to establish QN stability as in [17]. For single-class networks and single-server multi-class networks, the stability could be easily established through the routine conditions of traffic where intensity is expected less than one at all stations. But it is not true for multi-server multi-class QNs. This is proven by number of counter examples as in [18], [19], [20], [21], [22] & [23].

The fact has been established by these counter examples that traffic intensity may not be the only network factor responsible for affecting the stability but there are others as well. These are as under:-

·   The policy of scheduling

·   The network routing

·   The processes of routing

·   At one server classes have different service rates

·   The arrivals are dependent

Furthermore, another fact is established by these counter examples that resources are not utilized at their maximum. There are three conclusions drawn through this whole operation which are as follows:-

·   By increasing the capacity of service would not stabilize the network because of the stability of global region is not in continuation as explained in [18], [24].

·   Utilization does not have any concern with the stability of QN. There may be a bottleneck server due to the low utilization.

·   If customers are prioritized through scheduling then there will be a situation where few customers get service earlier than others. There will be few customers who keep on waiting in the queue for a longer period.  

B.    Assessment of Stability

The stability of QN can be determined through the following way as expounded in [25]:-

1) Sub-Networks:  Stability of network is based on the stability of all the stations in that network. Same way if a customer at a station is unstable then the station will be unstable and so the network will be as well.

2) Little’s Law:  The algorithm which is checking the stability of a QN is based on the time spent by the customers in the network. It also based on the number of customers present at one time in the network. Little law is applied either at the whole model of network or maybe to some part of it.

3) Linear Growth:  Through this, the customers’ growth rate in linear fashion can be determined. The results give out whether the network is stable or unstable.

C.   Acquisition of Stability

A detailed working has been done to acquire a stability formula in the field of QNs. These are highlighted in subsequent paragraphs in this sub-section.

Once the stability assessment is over with then it can be achieved by removing the hurdles. The performance of a QN can be gauged by two metrics; the throughput and the stability of the network. Both are inter-related to each other. If throughput is enhanced then the stability of the network is reduced and vice versa. Maximization of throughput is not possible in an unstable environment of QN, therefore, throughput could be compromised in order to attain stability as in [26].

Stability is also related to the effective rate of arrivals (internals and externals) of customers and the intensity of traffic. There are two types; path-wise stability and global or system stability. Path-wise stability is related to internal and external arrivals and this is considered weaker than system stability. However path-wise stability has to be achieved for global stability as in [27].

There is also another concept that exact conditions can’t be determined by which the stability of a QNs under prescribed scheduling policies can be judged, checked, and resolved. So the concept evolved around the un-decidability of QN algorithmically. This is true for both the infinite and finite sizes of the buffers as in [28].

 Another approach is considered in [29] where parallel server systems are in focus. To acquire the stability of a system the nominal condition of traffic is mandatory under the condition of generalized distribution of service and inter-arrival timing of customers.

If the queue’s length is time bounded with initial conditions then it is stable otherwise not. The stability of QNs is dependent upon the processes’ distributions stochastically as in [30].

In one of the considerations, it was assumed that the queue is having an infinite space. But the system would be stable if there is no increase in the queues. This is possible with some controlled policies. The policy of stabilizing the system is concerned with the rate of customers’ arrival the service rate provided to them. It also includes the policy of maximum throughput where a method of link activation is provided by the queueing model to stabilize the network as in [35].

In short, a lot of research work has been carried out to establish that queueing network stability can be achieved. All such experiments and their results are based on three networks namely Jackson, Generalized Jackson, and Kelly networks as in [31]. These networks less generalized are stable in an environment where invariant distribution is determined explicitly as in [32] & [33]. Whereas the Generalized Jackson network’s stability is based on the proof of Harris recurrence (positive) of the Markov process as in [34]. A Lyapunov function is constructed where Poisson arrivals with exponential service times are used to establish the stability of queueing networks which are multi-class as in [17].     

D. Proposed Solution

The research on the topic has been carried out by a number of researchers in the last three decades. Only a few worthwhile papers from 1992 till 2014 are referred here which have done remarkable research in the field of QNs stability as in [15], [35], [36], [37], [38], [39], [40], [41] & [42]. This paper has surveyed and highlighted the previous studies and suggests the following solution:-

·   By increasing the capacity of queues, more customers can be entertained.

·    By increasing the number of queues more customers can be entertained in less time frame.

·   By adding more servers in the service centers less time will be spent in executing more customers.

·   An algorithm can be devised which could speed up the service time at service centers.  

Nexus to above the proposals could be used in isolation or in combination as well as the capacity of buffers and the number of queues can be increased for clearing more jobs on a reduced scale of time. A faster algorithm with more number of servers in service centers is also a beneficial approach.

I.      Conclusion

This paper has been organized in order to highlight and survey the basic concepts of QNs along with existing scheduling policies and parameters to achieve better performance. It also mentions the factors required to maintain the stability of QNs and reasons for instability. Actually, the stability of the network depends upon load over the network. Whenever prescribed capacity of a buffer is full then arriving customers are piled up at queues and the system becomes unstable. Different scheduling policies or disciplines are tested and adopted to cater for such eventuality and it is observed that still system derail from the stability factor very often. Although a lot has been improved keeping in view where we stand in the 1990s and now in present-day but room for improvement is still there.   

In a nutshell, this paper encompasses QNs in general and their stability, instability factors along with a proposed solution in particular. 

References

[1] U. Schwiegelshohn and R. Yahyapout, “Analysis of First-Come-First-Serve Parallel Job Scheduling”, SODA, Zwsisk, 1998, pp. 1-10.

[2] A.G. Fraser and Bernardsville, “First-in, First-out (FIFO) Memory Configuration for Queue Storage”, USA, 1985, pp. 1-7.

[3] S. Lupetti and D. Zagorodnov, “Data Popularity and Shortest-Job-First Scheduling of Network Transfers”, Tromso Uni. Norway, 2006, pp. 1-7.

[4] P.J. Denning and J.P. Buzen, “The Operational Analysis of Queueing Network Models”, CSUR, vol. 10, no. 3, Sep. 1978, Purdue Uni. USA, pp. 1-37.

[5] S. Balsamo et. al. “Analysis of Queueing Networks with Blocking”, Springer, Stanford Uni. USA, 2001, pp. 8-9.

[6] N.C. Hock and S.B. Hee, “Closed Queueing Networks”, 2^nd ed. Singapore, 2008, pp. 169-214.

[7] H. Chen and D.D. Yao, “Fundamentals of Queueing Networks- Performance, Asymptotics, and Optimization”, Springer, New York, 2001, pp 21-23.

[8] W. Whitt, “The Queueing Network Analyzer”, TBSTJ, vol. 62, no. 9, Nov. 1983, USA, pp. 1-37.

[9] S. Ramesh and H.G. Perros, “A Multi-Layer Client-Server Queueing Network Model with Synchronous and Asynchronous Messages”, North Carolina Uni. USA, 1998, pp. 1-13.

[10] F. Baskett et. al. “Open, Closed, and Mixed Networks of Queues with Different Classes of Customers”, Taxas Uni. USA, 1975, pp. 1-13.

[11] “FIFO (computing and electronics)”, [online]. Available: https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics).

[12] “FIFO and LIFO Accounting”, [online]. Available: https://en.wikipedia.org/wiki/FIFO_and_LIFO_accounting.

[13] “Shortest Job Next”, [online]. Available: https://en.wikipedia.org/wiki/Shortest_job_next.

[14] “Processor Sharing”, [online]. Available: https://en.wikipedia.org/wiki/Processor_sharing.

[15] M. Bramson, “Stability of Queueing Networks”, Springer, Minnesota Uni. USA, 2008, pp. 24.

[16] E.D. Lazowska et. al. “Quantitative System Performance”, chap. 4, pub. Prentice-Hall, 1984, pp. 57- 68.

[17] P.R. Kumar and S.P. Meyn, “Stability of Queueing Networks and Scheduling Policies”, IEEE, TOAC, vol. 40, no. 2^nd Feb. 1995, USA, pp. 251-260.

[18] P.R. Kumar and T.I. Seidman, “Dynamic Instabilities and Stabilization
Methods in Distributed Real-Time Scheduling of Manufacturing Systems”, IEEE TOAC, vol. 35, Mar. 1990, USA, pp. 289-298.

[19] A.N. Rybko and A.L. Stolyar, “Ergodicity Stochastic Processes Describing Operations of Open Queueing Networks”, PIT, vol. 28, no. 3, 1992, pp. 199–220.

[20] T.I. Seidman, “First Come, First Served can be Unstable!” IEEE TOAC, vol. 39, no. 10, 1994, USA, pp. 2166–2171.

[21]      M. Bramson, “Instability of FIFO Queueing Networks”, TAAP, vol 4, no. 2, 1994, USA, pp. 414–431.

[22] M. Bramson, “Instability of FIFO Queueing Networks with Quick Service Times”, TAAP, vol. 4, no. 3, 1994, pp. 693–718.

[23] J. Banks and J.G. Dai, “Simulation Studies of Multiclass Queueing Networks”, IIE Trans. Vol. 29, 1997, pp. 213–219.

[24] A. Sharifnia, “Instability of the Join-the-Shortest Queue and FCFS Policies in Queueing Systems and their Stabilization”, INFORMS, vol. 45, no. 2, 1997, USA, pp. 309–314.

[25] J.R. Wieland et. al. “Queueing Network Stability: Simulation-Based Checking”, proc. of winter sim. Conf. Purdue Uni. USA, 2003, pp. 520-527.

[26] P. Chaporkar and S. Sarka, “Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems”, IEEE TOAC, vol. 53, no. 8, Sept. 2008, Pennsylvania Uni. USA, pp. 1913-1931.

[27] J.J. Hasenbein, “Stability, Capacity, and Scheduling of Multiclass Queueing Networks”, thesis, Georgia, 1998, chap. 3, pp. 21-27.

[28] D. Gamarnik and D. Katz, “On Deciding Stability of Multiclass Queueing Networks under Buffer Priority Scheduling”, TAAP, vol. 19, no. 5, 2009, USA, pp. 2008–2037

[29] G. Baharian and T. Tezcan, “Stability Analysis of Parallel Server Systems under Longest Queue First”, Springer, USA, 2011, pp. 258.  

[30] D. Armbruster et. al. “On the Stability of Queueing Networks and Fluid Models”, Eindhoven Uni. USA, 2010, pp. 1-8.

[31] H. Chen, “Fluid Approximations and Stability of Multiclass Queueing Networks: Work-Conserving Disciplines”, TAAP, vol. 5, no. 3, 1995, USA, pp. 637-665.

[32] J.R. Jackson, “Jobshop-like Queueing Systems”, JIMIMSORS, Uni. of California, 1963, USA, pp. 1-31.

[33] F.P. Kelly and J. Walrand, “Networks of Quasi-Reversible Nodes”, Springer, 1982, pp. 1-15.

[34] S.P. Meyn and D. Down, “Stability of Generalized Jackson Networks”, TAAP, vol. 4, no. 1, Uni. of Illinois,  USA, 1994, pp. 124-148.

[35] L. Tassiulas and A. Ephremides, “Stability Properties of Constrained Queueing Systems and Scheduling Polices for Maximum Throughput in Multi-hop Radio Networks”, IEEE, TOAC, vol. 37, no. 2, Dec. 1992, Maryland Uni., USA, pp. 1-14.

[36] C.S. Chang, “Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks”, IEEE, TOAC, vol. 39, 1994, USA, pp. 913-931.

[37] J. Dai and S. Meyn, “Stability and Convergence of Moments for Multiclass Queueing Networks via Fluid Limit Models”, IEEE, TOAC, vol. 40, 1995, USA, pp. 1889-1904.

[38] A.L. Stoylar, “Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm”, Springer, Queueing Syst. vol. 50, 2005, USA, pp. 401-457.

[39] J.G. Dai et. al. “Stability of Join the Shortest Queue Network”, Springer, Queueing Syst. vol. 57, USA, 2007, pp. 129-145.

[40] M. Bramson, “Stability of Join the Shortest Queue Network”, TAAP, vol. 21, no. 4, Uni. of Minnesota, USA, 2010, pp. 1568-1625.

[41] P. Wang and I.F. Akyildiz, “Network Stability of Cognitive Radio Networks in the Presence of Heavy Tailed Traffic”, Georgia, 2012, pp. 1-9.

[42] S.T. Maguluri et. al. “The Stability of Longest-Queue-First Scheduling with Variable Packet Sizes”, IEEE, TOAC, Uni. of Illinois, USA, 2014, pp. 1-8.

Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×

Polynomiography

Polynomiography: A Computational and Mathematical Perspective

By

Rana Sohail

MSCS (Networking), MIT

Abstract— Polynomiography is basically the study of art and science of visualization to make approximations for the complex polynomial’s zeros. The study revolves around the pictorial view of polynomials where the image is created and further be used in educational and scientific world. The applications created by polynomiography are very useful in the fields of art, education and science. This paper will make an endeavour to establish the relationship between the computational and mathematical aspects.

Keywords— Polynomiography, polynomials, art, science, mathematics,

I. INTRODUCTION

Before describing the polynomiography let’s discuss the polynomial as it can be defined as a finite collection of points in Euclidean Plane where these points are basically are the roots or zeros. These roots bifurcates the Euclidean Plane into independent territories which are determined by an iteration function. Now polynomiography can be described as the painting of these points in an ordered fashion thus making it an artwork. So polynomiography is the study of art and science of mental picture to make estimates for the complex polynomial’s zeros. The study encompasses the graphic view of polynomials in which the created images are used in the world of education and science. World of polynomiography is made up of two words ‘polynomial’ and ‘graphy’, the meaning is very prominent and that is polynomials are presented with the help of graphs. Actually we require specific algorithms to do the job.  Polynomial is an object which is based on the mathematical basic and fundamental class. The multiplication of algebraic expression is much faster through algorithm than before. Here the pixels are involved which may vary from hundred to millions. Today the computer makes it very easy to get the results. Millions of pixels are manipulated on the screen of a computer as in [1].

Polynomiography is the result of infinite number of iteration functions which are established for the purpose of approximation of the polynomial’s root-finding. Here the iteration function means the mapping of the plane into itself.    

The paper is organized in sections. In section II, Polynomiography base and its fields will be defined. In section III, relationship of mathematical concepts and polynomiography will be discussed. In Section IV, the discussion will be concluded.

II.      POLYNOMIOGRAPHY – THE BASE AND ITs FIELDS

A.    The Base

Once we take the polynomial

p(z)= a_nzⁿ+a_n−1zⁿ⁻¹ + ….+ a₁z + a₀;

where n ≥ 2, and the coefficients a_i are complex numbers. This problem presents the approximating roots of p(z). Here iteration function is operative which belongs to “Basic Family” as in [2]. Among others, Basic Family has two famous members namely Newton’s iteration function;

  

and Halley’s iteration function;

In both cases the upper and lower bounds are declared as U_m and L_m where m is a natural number and ≥ 2. The numbers are computable in terms of coefficient of p i.e. each root θ can have L_m≤θ ≤ U_m.

Polynomiography gives out the visualizations of such situations of Basic Family and its properties. 

B.    Fields

Polynomiography is useful in three important fields of life which are very famous, details are as under:-

(1)       Visual Art:             Polynomiography software is very useful; it works like a camera or musical instrument. Through it can draw simple as well as complex patterns of designs which can be comparable with any classic work of human.

Polynomiography is very useful in teaching the basics and professional artistic and mathematical concepts in the classroom at any level. There is no requirement of basic teaching of such software; even a beginner can handle it comfortably. An analogous image to the camera can be easily created digitally by it. It is all possible by using iteration functions by the software.

Polynomiography makes it possible to solve the issue of “reverse root-finding”. Here the roots of any polynomial can be found through iteration function and combination of desired colour scheme can create wonderful designs. Likewise, user can create images by putting the coefficients of the polynomial or zeros locations in the software. In the field of art, polynomiography can be specific in terms of creating images in following way as in [3]:-

  Polynomiographer uses one polynomial and produces a variety of images. This is possible because of the use of the variety of iteration functions.

  Polynomiographer can turn an ordinary image to a very attractive and beautiful image by using colours and imaginative creativity.

  Polynomiographer  can  combine  the  art  and mathematics by using either polynomials or iteration functions.

  Polynomiographer can use the already created polynomiographs and mixing of two or more can be done.

Figure 1 and 2 are examples of polynomiographic software creation.

(2)  Education:  Polynomiography can be very useful in the field of teaching. It is used to deploy and solve difficult theorems which are totally dealing with the polynomials. It is also helpful in the understanding of algebra and geometry. Figure 3 gives out Fundamental Theorem of Algebra visually as in [1]. It show the polynomiography of nine digit number.

Once  the  level  is  raised  to  higher  education, polynomiography software still has the command over calculus, numerical analysis, notion of convergence, limits, iteration functions, fractals, root-finding algorithms etc. 
(3)  Science: Polynomiography do have importance in the field of science because almost all the science theories are based on polynomials and if we know the roots of a polynomial then we can say that we know the polynomial as well.  In  science  special  polynomials  like  Legendre polynomials as in [4], Chebyshev polynomials as in [5], orthogonal polynomials as in [6] etc were difficult to be understood but polynomiography made it very easy and simple to understand. Figure 4 as in [1] gives some polynomiography for a polynomial arising in physics.

III. RELATIONSHIP OF  MATHEMATICAL  CONCEPTS AND

POLYNOMIOGRAPHY

A. Numeric Polynomiography
The use of polynomiography software application for numerical equations is very interesting. Here numbers can be encrypted with it. We can take the examples of ID or credit card numbers that can be divided into two dimensional images which can be resembled as a fingerprint. Now different fingerprints can be presented by different numbers. We can take the example of number a 8 a 7 …a 0 which can be identified by the polynomial P(z) = a 8 z 8 +….+ a 1 z + a 0 as in [1]. 
Finding square root of numbers is another way of handling through polynomiography which is a very interesting and simple task. Here polynomial equations are approximated by square rooting through images as in [7]. Figure 5 shows the graphical view of computing square root of two.

Likewise irrational numbers, complex numbers and iterative methods can be more elaborative and understandable with the help of polynomiography as never before as explained in [7].
B. Basins of Attractions and Voronoi Region of Polynomial Roots
The basins of attraction of a root in relation with iteration function are the regions in the complex plane as shown in figure 6

It is basically the set of initial conditions which leads to long time behaviour approaching the attractor. So the better quality of long time motion of a system could be different. It depends upon the initial conditions as the attractors may be corresponding to periodic or quasiperiodic or chaotic behaviours of different types. In a state plane a region presenting the basin of attraction will be different because it varies from system to system. These attractions can be drawn graphically but not with ease and if at any stage of drawing a minute mistake occurs then whole process would be a waste. Polynomiography made it so easy and simple that software draws all of it once the initial conditions are set in the prescribed regions.
Julia set as defined in [8] of the polynomial roots has the nature of fractal. Images of basins of attractions of Newton's method are very similar to that of some special polynomials. Mathematical analysis of complex iterations can be dealt with polynomiography as in [9].
Voronoi Region of polynomial roots can be defined as a diagram which divides the space into a number of regions. Points in each region are set at initial stage and all points are set in such a way that they are placed closer to each other. These regions are also known as voronoi cells. These diagrams are very helpful in the fields of science, technology and artwork.
There are number algorithms which find out the Voronoi regions by computation like Divide and Conquer, Brute Force, Fortune’s Line Sweep etc. Once computing intersection of half planes the time taken will be O (n 2 log n) and while proving lower bounds require Ω (n log n) and so on. 
Figure 7 shows the space divided into twenty regions with twenty points or cells placed in them in a way to be closed to each other. This sort of display will be very easy to depict with the help of polynomiograhy software.

C. Root Sensitivity
The n roots of a polynomial of degree n depend continuously on its coefficients. It can be explained as a polynomial root is a zero of the polynomial function and any non – zero polynomial and its degree has equal roots. The equation polynomial f of degree two will be:-

f (x) = x 2 – 5x + 6

have two roots 2 and 3, since

f (2) = 2 2 – 5.2 + 6 = 0 and

f (3) = 3 2 – 5.3 + 6 = 0

in case the function has to map real numbers to another real numbers then their zeros will be the x-coordinates of the points where their graph will be meeting the x-axis as explained in [10].
Polynomial roots are very sensitive to even small changes which are if carried out in their coefficients. We may take the example of

p(z)=(z−1)(z−2)…..(z−n)

suppose n = 7 then

p(z)=z 7  − 28z 6 + 322z 5 − 1960z 4 + 6769z 3 − 13132z 2 + 13068z – 5040

If we change coefficient of z 6 from −28 to −28:002 then this small change can have a large change in the roots. Some real roots will become complex. This aspect can’t be visualized in advance once solving the equation but polynomiography made it possible to have advance information on this important aspect as in [11]. Figure 8 shows the changes in the roots as the coefficient of z 6 is decreased.

D. Complex Multiplication

Multiplication of complex numbers as in [12] is an important subject and polynomiography made it very easy to understand, we can take an example
Suppose two complex numbers z 1 = (a+bi) and z 2 = (c+di). They can be added as (a+b) + i(c+d), and their product is said to be (ac−bd)+i(ad +bc).
We take another example to explain it further in detail. Once the complex plane is multiplied by i then the result will be (3+4i) x i = 3i + 4i 2 and i 2 = -1, so: 3i + 4i 2 = -4 + 3i, figure 9 shows the equation in complex plane.

One important thing can be observed that rotation of angle is right angle (90° or π/2) and same will be the results once same multiplications are carried out.

(-4 + 3i) x i = -4i + 3i 2 = -3 - 4i,

(-3 - 4i) x i = -3i - 4i 2 = 4 - 3i and

(4 - 3i) x i = 4i - 3i 2 = 3 + 4i

So the results are clear that rotation has completed a circle and it finished where it has started. Figure 10 shows a very clear right angle and rotation. Such complex plane calculations can confuse the readers but polynomiography made very simple, anyone with little knowledge can easily understand it.

IV. CONCLUSION

In this paper polynomiography is discussed in detail. The concept of polynomial study in the fields of art, science and education has been highlighted. The mathematical concepts have specially been discussed. The mathematical concepts which are ambiguous and very difficult to grasp by the students are given a new dimensional world where these conceptual thinking has a platform of graphical view. The calculations for the polynomial roots and their coefficients are if carried out with the help of computer or calculator will be accurate but there are lots of chances where their execution on a graph paper would be a disaster with a minute mistake. These fields were very difficult to understand but polynomiography made it very simple and easy to understand. Polynomials may be simple or complex both can be dealt very intelligently by the polynomiography. This paper has the intentions to clear the basic concepts of the beginners in the field of Polynomiography in a befitting manner.

REFERENCES

[1]  Bahman Kalantari, “Polynomiography - A New Intersection between Mathematics and Art”, Department of Computer Science, Rutger University, USA, 2000, pp. 1.
[2]  Bahman Kalantari, “The Fundamental Theorem of Algebra and Iteration Functions”, Department of Computer Science, Rutger University, USA, 2003, sec. III and sec. VII.
[3]  Bahman Kalantari, “Polynomiography and Applications in Art, Education, and Science”, Department of Computer Science, Rutger University, USA, 2003, para 3.
[4]  J.C. Mason and D.C. Handscomb, “Chebyshev Polynomials”, New York: Washington D.C, CRC Press LLC, 2003, Ch. 1. 
[5]  Harry Bateman, “Higher Transcendental Functions”, vol. II, New York,
Toronto, London, McGral-Hill Book Company inc, 1953, Ch. 10, pp.178-182
[6]  H.L. Krall and Orrin Frink, “A New Class of Orthogonal Polynomials: The Bessel Polynomials”,  Transactions of the American Mathematical Society, 1949.
[7]  Bahman Kalantari, “A New Visual Art Medium: Polynomiography” Rutgers University, Computer Graphics, Vol. 38 No. 3 Aug. 2004, ACM SIGGRAPH, Los Angeles, California, USA, Art. 21, pp. 21-23
[8]  Wikipedia, The Free Encyclopaedia website, “Julia Set”. [Online]. Available: http://en.wikipedia.org/wiki/Julia_set
[9]  Bahman Kalantari, “The Art in Polynomiography of Special Polynomials”, Department of Computer Science, Rutger University, USA, 2003.
[10] Wikipedia, The Free Encyclopaedia website, “Zero of a function”. [Online]. Available: http://en.wikipedia.org/wiki/Polynomial_roots
[11] Bahman Kalantari et al., “Animation of Mathematical Concepts using Polynomiography”, Department of Computer Science, Rutger University, USA, 2004.
[12] Math is Fun Advanced website, “Complex Number Multiplication”. [Online].  Available:  http://www.mathsisfun.com/algebra/complex-number-multiply.html

Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×