2011-01-30

Z-matrix


 the class of Z-matrices are those matrices whose off-diagonal entries are less than or equal to zero; that is, a Z-matrix Z satisfies
Z=(z_{ij});\quad z_{ij}\leq 0, \quad i\neq j.
Note that this definition coincides precisely with that of a negated Metzler matrix or quasipositive matrix, thus the term quasinegative matrix appears from time to time in the literature, though this is rare and usually only in contexts where references to quasipositive matrices are made.
The Jacobian of a competitive dynamical system is a Z-matrix by definition. Likewise, if the Jacobian of a cooperative dynamical system is J, then (−J) is a Z-matrix.
Related classes are L-matricesM-matricesP-matricesHurwitz matrices and Metzler matricesL-matrices have the additional property that all diagonal entries are greater than zero. M-matrices have several equivalent definitions, one of which is as follows: a Z-matrix is an M-matrix if it is nonsingular and its inverse is nonnegative. All matrices that are both Z-matrices and P-matrices are nonsingularM-matrices.

M-matrix


 An M-matrix is a Z-matrix with eigenvalues whose real parts are positive. M-matrices are a subset of the class of P-matrices, and also of the class of inverse-positive matrices (i.e. matrices with inverses belonging to the class of positive matrices).[1]
A common characterization of an M-matrix is a non-singular square matrix with non-positive off-diagonal entries and all principal minors positive, but many equivalences are known. The name M-matrix was seemingly originally chosen by Alexander Ostrowski in reference to Hermann Minkowski.[2]
A symmetric M-matrix is sometimes called a Stieltjes matrix.
M-matrices arise naturally in some discretizations of differential operators, particularly those with a minimum/maximum principle, such as the Laplacian, and as such are well-studied in scientific computing.
The LU factors of an M-matrix are guaranteed to exist and can be stably computed without need for numerical pivoting, also have positive diagonal entries and non-positive off-diagonal entries. Furthermore, this holds even for incomplete LU factorization, where entries in the factors are discarded during factorization, providing useful preconditioners for iterative solution.

2009-10-26

Internet y la ciencia

Con solo una PC y conexión a Internet es posible participar en esfuerzos científicos de alcance global.

Explorar el universo

En el sitio www.galaxyzoo.org puedes ayudar a los astrónomos a explorar el universo. El sitio contiene un cuarto de millón de imágenes obtenidas por un telescopio robótico ( Sloan Digital Sky Survey) y voluntarios pueden ayudar a clasificar las imágenes.

La búsqueda de número primos

 GIMPS provee programas que se pueden usar como screen savers y buscan números primos. Inclusive hay recompensa económica para motivar el desarrollo de esta tecnología a través de EFF Cooperative Computing Awards para el que encuentre primero:

2009-09-04

La escalabilidad del computo

Cuando estaba en la escuela, hace algunos años, había gran efervescencia sobre el tema del computo paralelo, de hecho mi tesis doctoral es sobre este tema. Recuerdo que comentado sobre   las posibilidades del paralelismo con mi asesor, me dijo que desde un punto de vista teórico el  computo paralelo no era importante porque no cambiaba los limites de escalabilidad impuestos por los problemas NP.


Ahora nos encontramos en un resurgimiento de los enfoques del computo distribuido debido al abaratamiento del hardware y la cada vez mayor disponibilidad de conexiones de banda ancha. Por lo tanto la cuestión de algoritmos eficientes para problemas NP y la corroboración teórica de NP ǂ P se ha convertido en uno de los problemas primordiales de la teoría y practica del computo.

Referencias

2009-08-22

La aritmética de Trachtenberg

Así como Viktor Emil Frankl desarrollo la logoterapia para superar los rigores de los campos de concentración Nazi, Jakow Trachtenberg ocupo su mente en desarrollar un sistema de aritmética mental al verse en la misma situación.

El sistema Trachtenberg de rápido cálculo mental, similar a las matemáticas Védicas, consiste en un conjunto de patrones para realizar operaciones aritméticas. Los algoritmos más importantes son multiplicación,división, y adición. El método también incluye algoritmos especializados para realizar multiplicaciones por números entre 5 y 13.

Multiplicación por 11

Abusando de la notación

(11)a = 11Σai10i =

an10n+1 + [Σj=0n-1(aj+aj+1)10j ]+ a0

Multiplicación por 12

(12)a = 12Σai10i =

an10n+1 + [Σj=0n-1 (aj+2aj+1)10j ]+ 2a0

Multiplicación por 6

Definiendo

bj = aj/2, donde / denota división entera

cj = aj mod 2

tenemos

aj = 2bj + cj

(6)a = (10/2)Σai10i  + Σai10i =

Σbi10i+1 + Σ(ai + 5ci)10i

bn10n+1 + [Σj=1n(aj + 5cj + bj-1)10j ]+ (a0 + 5c0)

Expresando el algoritmo en python:

def x6(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result




Multiplicación por 7



De manera similar al caso anterior:




aj = 2bj + cj



(7)a = (10/2)Σai10i  + Σ2ai10i =



Σbi10i+1 + Σ(2ai + 5ci)10i



bn10n+1 + [Σj=1n(2aj + 5cj + bj-1)10j ]+ (a0 + 5c0)




Expresando el algoritmo en python:



def x7(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(2*digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result


Multiplicación por 5



De manera similar al caso anterior:




aj = 2bj + cj



(5)a = (10/2)Σai10i   =



Σbi10i+1 + Σ(5ci)10i



bn 10n+1 + [Σj=1n(5cj + bj-1)10j ]+ (5c0)




Expresando el algoritmo en python:



def x5(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result


Multiplicación por 9



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a




tenemos




(9)a = 10a –a =



10a –a + b – b =



10a + b - 10n+1 =



(an – 1)10n+1 + [Σj=1n(bj + aj-1)10j ]+ (b0 )




Expresando el algoritmo en python:



def x9(number):
previous = number%10
result = 10 - previous
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(9 - digit + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-1) * power_of_10 +
result
return result


Multiplicación por 8



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a




tenemos




(8)a = 10a –2a =



10a –2a +2 b – 2b =



10a + 2b – (2)10n+1 =



(an – 2)10n+1 + [Σj=1n(2bj + aj-1)10j ]+ (2b0 )




Expresando el algoritmo en python:



def x8(number):
previous = number%10
result = 2*(10 - previous)
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(2*(9 - digit) + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-2) *
power_of_10 + result
return result


Multiplicación por 3 y por 4



Los algoritmos para multiplicar por 3 y por 4 combinan las ideas usadas en la multiplicación por 5 y por 9.



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a



ai = 2ci + di, donde



ci = ai/2



di = ai mod 2




tenemos




(4)a = 5a –a =



10c + 5d + b - 10n+1



(3)a = 5a –2a =



10c + + 5d + 2b – (2)10n+1




Expresando los algoritmos en python:



def x3(number):
digit = number%10
result = 2*(10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=(2*(9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-2) * power_of_10 + result
return result

def x4(number):
digit = number%10
result = (10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=((9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-1) * power_of_10 + result
return result


Referencias