PDF de programación - Programación: operación axpy

Programaci´on: operaci´on axpy

Objetivos. Programar una funci´on que calcule αx + y, donde α ∈ R, x, y ∈ Rn.

Requisitos. Programaci´on de funciones con arreglos y ciclos for; creaci´on de vectores
pseudoaleatorios; medici´on del tiempo de ejecuci´on.

1. Problema: operaci´on axpy. En alg´un lenguaje de programaci´on escribir una funci´on
que calcule el vector αx + y, donde α ∈ R, x, y ∈ Rn.

Entrada: α ∈ R, x, y ∈ Rn.

Condici´on que debe cumplir la entrada: los vectores dados x, y son de la misma
longitud. No tiene que verificar esta condici´on.

Salida: el vector αx + y.

Soluci´on en el lenguaje de Matlab (guardar en el archivo axpy.m):

function r = axpy(a, x, y),

n = length(x);
r = zeros(n, 1);
for j = 1 : n,

r(j) = a * x(j) + y(j);

end

end

2. An´alisis de complejidad. Calcular el n´umero de operaciones de multiplicaci´on en el
algoritmo anterior. La respuesta es un polinomio de la variable n. Calcular el n´umero de
operaciones de adici´on.

3. Pruebas con vectores peque˜nos. Escribir un programa que llame a la funci´on del
ejercicio anterior, aplic´andola a los siguientes datos:

 ,

 3−4

1

 .

 2

5−2

α = 5,

x =

y =

Nuestra funci´on axpy debe regresar el mismo resultado que la expresi´on alpha * x + y.
Soluci´on en el lenguaje de Matlab (guardar en el archivo testaxpy1.m):

function [] = testaxpy1(),

alpha = 5; x = [3; -4; 1]; y = [2; 5; -2];
display(axpy(alpha, x, y));
display(alpha * x + y);

end

Programaci´on: operaci´on axpy, p´agina 1 de 2

4. Prueba con un vector corto pseudoaleatorio.

function [] = testaxpy2(),

alpha = 2 * rand() - 1;
x = 2 * rand(n, 1) - ones(n, 1);
y = 2 * rand(n, 1) - ones(n, 1);
display(alpha);
display(x);
display(y);
p = axpy(alpha, x, y);
display(p);
q = alpha * x - y;
display(norm(p - q));

end

5. Pruebas con vectores pseudoaleatorios largos. En alg´un lenguaje de progra-
maci´on escribir un programa que genere vectores de tama˜nos grandes: n = 104, luego
n = 105, luego n = 106, aplique a estos vectores la funci´on del Ejercicio 1 y mida el tiem-
po de ejecuci´on. Las computadoras contemporaneas realizan una operaci´on de tipo axpy
muy r´apidamente, a´un cuando n es grande. Para medir mejor los intervalos de tiempo,
repetimos cada prueba 10 veces. Soluci´on en Matlab (guardar en el archivo testaxpy3.m):

function [] = testaxpy3(),

nrep = 10;
for n = [10000, 100000, 1000000],

2 * rand() - 1;

display(n);
alpha =
x = 2 * rand(n, 1) - ones(n, 1);
y = 2 * rand(n, 1) - ones(n, 1);
t1 = cputime();
for rep = 1 : nrep,

p = axpy(alpha, x, y);

end
t2 = cputime();
display((t2 - t1) / nrep);

end

end

¿C´omo se cambia el tiempo de ejecuci´on cuando n se multiplica por 10?

Programaci´on: operaci´on axpy, p´agina 2 de 2