Polynomials - Revision history

Admin: /* Multiplication */

2017-08-15T22:35:25Z

Multiplication

← Older revision		Revision as of 22:35, 15 August 2017
Line 106:		Line 106:

	However, with some care, multiplication can be done in <math>O(N \log N)</math> time.		However, with some care, multiplication can be done in <math>O(N \log N)</math> time.

			[[Divide and Conquer/Polynomial Multiplication]]

	=Teaching Computer Science with Polynomials=		=Teaching Computer Science with Polynomials=

Admin: /* Representation */

2017-08-15T22:34:51Z

Representation

← Older revision		Revision as of 22:34, 15 August 2017
Line 52:		Line 52:
	The Fundamental Theorem of Algebra [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.		The Fundamental Theorem of Algebra [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.

	The problem with the roots representation is, there is no general method to go from coefficients to roots - we have formulas for special cases (degree 2, 3, and 4) but no formula for degree > 5 (a result of the Abel-Ruffini Theorem [~~http~~://~~mathworld~~.~~wolfram~~.~~com~~/Abel~~-RuffiniTheorem.html~~]).		The problem with the roots representation is, there is no general method to go from coefficients to roots - we have formulas for special cases (degree 2, 3, and 4) but no formula for degree > 5 (a result of the Abel-Ruffini Theorem [https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem]).

	We will cover, below, the relationship between operations and representations.		We will cover, below, the relationship between operations and representations.

Admin: /* Representation */

2017-08-15T22:14:25Z

Representation

← Older revision		Revision as of 22:14, 15 August 2017
Line 48:		Line 48:
	* Coefficient vector <math> \langle a_0, a_1, a_2, \dots, a_{n-1} \rangle</math>		* Coefficient vector <math> \langle a_0, a_1, a_2, \dots, a_{n-1} \rangle</math>
	* Roots/sequence of roots <math>\langle r_0, r_1, r_2, \dots, r_{n-1} \rangle</math>		* Roots/sequence of roots <math>\langle r_0, r_1, r_2, \dots, r_{n-1} \rangle</math>
	* Samples <math>(x_k, y_k) \~~qquad~~ A(x_k) = y_k</math>		* Samples <math>(x_k, y_k) \quad \rightarrow \quad A(x_k) = y_k</math>

	The Fundamental Theorem of Algebra [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.		The Fundamental Theorem of Algebra [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.

Admin: /* Representation */

2017-08-15T22:14:08Z

Representation

← Older revision		Revision as of 22:14, 15 August 2017
Line 50:		Line 50:
	* Samples <math>(x_k, y_k) \qquad A(x_k) = y_k</math>		* Samples <math>(x_k, y_k) \qquad A(x_k) = y_k</math>

	The [[Fundamental Theorem of Algebra]] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.		The Fundamental Theorem of Algebra [https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.

	The problem with the roots representation is, there is no general method to go from coefficients to roots - we have formulas for special cases (degree 2, 3, and 4) but no formula for degree > 5 (a result of the Abel-Ruffini Theorem).		The problem with the roots representation is, there is no general method to go from coefficients to roots - we have formulas for special cases (degree 2, 3, and 4) but no formula for degree > 5 (a result of the Abel-Ruffini Theorem [http://mathworld.wolfram.com/Abel-RuffiniTheorem.html]).

	We will cover, below, the relationship between operations and representations.		We will cover, below, the relationship between operations and representations.

Admin at 22:06, 15 August 2017

2017-08-15T22:06:32Z

← Older revision		Revision as of 22:06, 15 August 2017
Line 4:		Line 4:
	- Box and Draper, ''Empirical Model-Building and Response Surfaces''		- Box and Draper, ''Empirical Model-Building and Response Surfaces''
	}}		}}



	=Mathematics=		=Mathematics=

Admin: /* Algorithms */

2017-08-15T22:06:09Z

Algorithms

← Older revision		Revision as of 22:06, 15 August 2017
Line 33:		Line 33:
	=Algorithms=		=Algorithms=

	~~Define~~ a polynomial as:		Algebraic definition of a polynomial:

	<math>		<math>
	A(x) = a_0 + a_1 x_1 + a_2 x_2^2 + \dots + a_{n-1} x^{n-1}		A(x) = a_0 + a_1 x_1 + a_2 x_2^2 + \dots + a_{n-1} x^{n-1}
	</math>		</math>

			==Representation==

			We can represent a polynomial in a couple of ways, each useful in various situations. Keep in mind, the ability or inability to convert between different representations is crucial to algorithm design.

			Three ways:
			* Coefficient vector <math> \langle a_0, a_1, a_2, \dots, a_{n-1} \rangle</math>
			* Roots/sequence of roots <math>\langle r_0, r_1, r_2, \dots, r_{n-1} \rangle</math>
			* Samples <math>(x_k, y_k) \qquad A(x_k) = y_k</math>

			The [[Fundamental Theorem of Algebra]] tells us that any polynomial of degree n has n roots (if we include roots with multiplicity). FTA proven by Gauss; uniqueness of representation proven by Legendre.

			The problem with the roots representation is, there is no general method to go from coefficients to roots - we have formulas for special cases (degree 2, 3, and 4) but no formula for degree > 5 (a result of the Abel-Ruffini Theorem).

			We will cover, below, the relationship between operations and representations.

	==Operations==		==Operations==

Admin: /* Multiplication */

2017-08-15T21:02:12Z

Multiplication

← Older revision		Revision as of 21:02, 15 August 2017
Line 88:		Line 88:
	If we had the roots of each polynomial, we could do this in O(1) time by just concatenating the roots of each polynomial. That's tough to beat - except for the fact that getting from coefficients is impossible if the degree is higher than 4 - which makes this technique more of a math trivia question.		If we had the roots of each polynomial, we could do this in O(1) time by just concatenating the roots of each polynomial. That's tough to beat - except for the fact that getting from coefficients is impossible if the degree is higher than 4 - which makes this technique more of a math trivia question.

	~~With~~ some care, multiplication can be done in <math>O(N \log N)</math> time.		However, with some care, multiplication can be done in <math>O(N \log N)</math> time.

	=Teaching Computer Science with Polynomials=		=Teaching Computer Science with Polynomials=

Admin: /* Algorithms */

2017-08-15T21:02:02Z

Algorithms

← Older revision		Revision as of 21:02, 15 August 2017
Line 46:		Line 46:
	* Multiplication of two polynomials		* Multiplication of two polynomials

	~~==Evaluation==~~		One of the challenges with implementing fast and efficient algorithms for each of these operations is, each operation has an ideal choice for how to represent the polynomial - and it's differnet for each operation.

	To evaluate a polynomial given its coefficients~~, we can evaluate the polynomial with~~ Horner's Rule:		For example, to add two polynomials in linear time, the coefficient vector representation is the easiest - then addition can be performed by adding corresponding vector elements. But to multiply two polynomials in linear time, the root representation (representing a polynomial using a vector of roots) is the fastest way - then multiplication is as simple as concatenating the roots.

			===Evaluation===

			It's easy to come up with an inefficient and slow algorithm for evaluation - evaluate the polynomial exactly as it is written:

			<math>
			A(x) = a_0 + a_1 x_1 + a_2 x_2^2 + \dots
			</math>

			However, while nominally linear, this procedure is very inefficient and redundant.

			A better way to evaluate a polynomial given its coefficients is to use Horner's Rule:

	<math>		<math>
Line 54:		Line 66:
	</math>		</math>

	This is an O(N) algorithm~~, much faster than evaluating each power of x separately, and adding all the terms together~~.		This is an O(N) algorithm.

	==Addition==		===Addition===

	To add two polynomials, <math>C(x) = A(x) + B(x)</math>,		To add two polynomials, <math>C(x) = A(x) + B(x)</math>, simply add together their coefficients. In this case, the coefficient representation is the best to use, as the corresponding elements of their vectors can be added in linear time for an overall <math>O(N)</math> addition algorithm.

	==Multiplication==		===Multiplication===

	Multiplication is an extremely useful operation - principally because it is equivalent to the ''convolution'' operation.		Multiplication is an extremely useful operation - principally because it is equivalent to the ''convolution'' operation.

	~~This~~ gets rather complicated rather quickly. There is not an easy way to do this because we have lots of interacting terms. (One constant term, but two linear terms; three quadratic terms; four cubic terms; etc.)		Using the coefficient representation, or the "classic" polynomial representation, this gets rather complicated rather quickly. There is not an easy way to do this because we have lots of interacting terms. (One constant term, but two linear terms; three quadratic terms; four cubic terms; etc.)

	General form: the kth term will be the sum over all the various combinations of coefficients that sum to k		General form: the kth term's coefficient will be the sum over all the various combinations of coefficients that sum to k:

	<math>		<math>
Line 72:		Line 84:
	</math>		</math>

	Total time to do this? Each term takes linear time (this is like a nested for loop), so the total time is <math>O(N^2)</math>.		Total time to do this? Each term takes linear time (this grows like a nested for loop), so the total time is <math>O(N^2)</math>. But this is "vanilla" polynomial multiplication.

			If we had the roots of each polynomial, we could do this in O(1) time by just concatenating the roots of each polynomial. That's tough to beat - except for the fact that getting from coefficients is impossible if the degree is higher than 4 - which makes this technique more of a math trivia question.

	~~"Vanilla" polynomial multiplication therefore takes <math>O(N^2)</math>. But with~~ some care, it can be done in <math>O(N \log N)</math> time.		With some care, multiplication can be done in <math>O(N \log N)</math> time.

	=Teaching Computer Science with Polynomials=		=Teaching Computer Science with Polynomials=

Admin: /* Computer Science Teaching */

2017-08-15T20:14:47Z

Computer Science Teaching

← Older revision		Revision as of 20:14, 15 August 2017
Line 76:		Line 76:
	"Vanilla" polynomial multiplication therefore takes <math>O(N^2)</math>. But with some care, it can be done in <math>O(N \log N)</math> time.		"Vanilla" polynomial multiplication therefore takes <math>O(N^2)</math>. But with some care, it can be done in <math>O(N \log N)</math> time.

	=Computer Science ~~Teaching~~=		=Teaching Computer Science with Polynomials=

	==Teaching Inheritance with Polynomials==		==Teaching Inheritance with Polynomials==

Admin: /* Multiplication */

2017-08-15T20:13:53Z

Multiplication

← Older revision		Revision as of 20:13, 15 August 2017
Line 72:		Line 72:
	</math>		</math>

	Total time to do this? Each term takes linear time (this is like a nested for loop), so the total time is O(N^2).		Total time to do this? Each term takes linear time (this is like a nested for loop), so the total time is <math>O(N^2)</math>.

	~~"Vanilla" polynomial multiplication therefore takes O(N^2). But with some care, it can be done in O(N log N) time.~~


			"Vanilla" polynomial multiplication therefore takes <math>O(N^2)</math>. But with some care, it can be done in <math>O(N \log N)</math> time.

	=Computer Science Teaching=		=Computer Science Teaching=