THMMY.gr

Εδώ συζητάμε για την 2η εργασία που έχει ανεβει στο elearning.

Προθεσμία: Παρασκευή, 20 Απρίλιος 2018, 12:00 πμ

Στο πρώτο ερώτημα τι εννοούν ; Να ψάξουμε και να βρούμε έναν αλγόριθμο που κάνει αυτόν τον πολλαπλασιασμό σε O(nlogn) ; Ή θέλουν κάποιον συγκεκριμένο τρόπο που έχουν στις διαφάνειες ;

Εχω ακριβως την ιδια απορια  :)  :)  :)

Όταν πάω να δημιουργήσω τον T πίνακα με την τρίτη εντολή του πρώτου ερωτήματος σην εκφώνηση της εργασίας και έχω για παράδειγμα n = 2^20 και m = 2^17 δεν μπορεί να δημιουργηθεί ο πίνακας Τ και έχω το εξής error:

Out of memory. Type HELP MEMORY for your options.

Error in toeplitz (line 40)
ij = (0:m-1)' + (p:-1:1);               % Toeplitz subscripts

Error in first (line 9)
T = toeplitz( u(m:n), u(m:-1:1) );

Έχει κανείς καμιά ιδέα πώς να το διορθώσω ;

σου λεει για n μεχρι 8000 (η καπου εκει δεν θυμαμαι ακριβως) να παρουσιάσεις αποτελεσματα, αρα ειναι λογικό πιστεύω

Από το ερώτημα πάντως καταλαβαίνω ότι εννοεί να γράψουμε τον αλγόριθμο για m <= n <= 2^24 αρχικά και στη συνέχεια να παρουσιάσουμε τα αποτελέσματα που λες.

Στο πρωτο ερωτημα εχει καταφερει κανεις να παρακαμψει το προβλημα οτι ο T δεν ειναι τετραγωνικος? Βρηκα τον αλγοριθμο για Toeplitz-vector multiplication αλλα εχει σαν προϋπόθεση ο T να ειναι nxn πινακας :-\

Ίσως αν τον γέμιζες με μηδενικά ώστε να γίνει τετραγωνικός  ; Μια σκέψη χωρίς να έχω δοκιμάσει κάτι...

δεν ζηταμε μια παραταση..?

Ναι, παιδιά να ζητήσουμε!

+1

Παιδες διαβασα σε ενα σχολιο καποιου στο mathworks οτι οσο και να χτυπιομαστε δε μπορουμε να φτιαξουμε αλγοριθμο που εκτελει πολ/μο matrix*vector γρηγοροτερα απο οτι το κανει η πραξη A*x του ματλαμπ γιατι το ματλαμπ χρησιμοποιει δικες του βιβλιοθηκες που το εκτελουν γρηγορα. Δεν ελεγε βεβαια αν το κανει σε nlogn αλλα οποιον απλουστερο κωδικα δοκιμασα ηταν υπερβολικα πιο αργος. Εχω την αισθηση οτι δε θελει γραψουμε τον κωδικα για το nlogn αλλα τον κωδικα για την "αργη" περιπτωση και να τα συγκρινουμε. Με καθε επιφυλαξη ο,τι εχω γραψει..
Φιλε σχετικα με το σφαλμα για το ερωτημα με το u(n:m) κλπ απλως δοκιμασε 1.πιο μικρες τιμες στα m,n και 2. μικροτερη την ΑΠΟΣΤΑΣΗ των m,n
Εγω εχω φαει κολλημα στο ερωτημα (β)iii ...δεν μπορω να καταλαβω πώς σκατα βγαινει
Επισης στο ερωτημα (γ) εχετε καταλαβει πώς χρησιμοποιουμε το αρχειο plant.p? Εννοω τι ορισματα παιρνει κλπ?

στο β και οι 4 μεθοδοι (i, ii, iii, iv) πρεπει να μας δινουν το ιδιο ή παραπλησια αποτελεσματα, ετσι δεν ειναι;

Πήρε παράταση !

Δε σου ζητάει να βρεις γρηγορότερο αλγόριθμο πολλαπλασιασμού πινάκων. Επίσης γνωστός O(nlgn) αλγόριθμος πολλαπλασιασμού πινάκων δεν υπάρχει.

Μαθηματικά σου ζητάει να βρεις έναν domain specific αλγόριθμο που να προσεγγίζει το γινόμενο με κόστος O(nlgn). Δηλαδή να καταλήξεις στο χαρτί σε μια σχέση που προσεγγίζει το y=Tw και η οποία αλγοριθμικά υπολογίζεται σε O(nlgn). Μετά θα κάνεις και τον κανονικό πολλαπλασιασμό και θα βρεις το σφάλμα για να δεις αν όντως τελικά με την προσέγγιση δε χάνεις και πολύ σε ακρίβεια ενώ γλιτώνεις πολύ σε υπολογιστικό κόστος.

Καταλαβε κανεις με τι ισουται το d(n)  εκει με το plant.p? Επισης μαθαμε τι ορισματα παιρνει το plant.p?

μαλλον θα επρεπε να εχει δοθει το παρακατω
(μου το εδωσε παλιοτερος)

Στο δεύτερο ερώτημα το αποτέλεσμα για το i) που χρησιμοποιώ τη συνάρτηση conv() μου βγάζει πίνακα με διπλάσιες γραμμές απ' ότι οι τρόποι του ii) και του iv). Είναι λογικό αυτό ή κάνω κάποιο λάθος ;

.
κανε zero padding, Δηλαδή πρόσθεσε μηδενικά στους πίνακες για να έχουν το μέγεθος του τελικού σηματος και μετα κανε πραξεις.

Γενικά η συνέλιξη σημάτων δεν δίνει ίδιου μήκους σήμα με τα αρχικά.

Ρε παιδιά εμένα ότι είσοδο και να βάλω στο plant.p μου πετάει σφάλμα


Ιndex exceeds matrix dimensions.

Error in plant (line 25)


Τρέχει σε κανέναν; Εγώ έβαλα σήματα σε στήλη/σειρά, τιμές, μεγάλες μικρές, θετικές αρνητικές... Τα ίδια.  :'(

στο 1ο και στο 2ο ερώτημα μπορουμε να χρησιμοποιησουμε την fft() του ματλαμπ γιατι αναφέρει μόνο στο 3ο  ερωτημα οτι μπορουμε να τη χρησιμοποιησουμε???

Μπορείς να τη χρησιμοποιήσεις σύμφωνα με απάντηση σε σχετικό μειλ.

Παιδιά εγώ καταρχάς δεν μπορώ να χρησιμοποιήσω το plant.p γιατι μου πετάει seg fault...
Επίσης, το LMS μου βγαζει πολύ κακά αποτελέσματα γενικά αν το δοκιμάσω σε δικό μου σύστημα που έκανα για τεστ.. Έχω την εντύπωση ότι δεν βελτιώνεται γιατι δεν έχω κάποιο λάθος...
Αυτό μας ενδιαφέρει γενικά; Ή μας νοιάζει μόνο το πιο συμφέρον υπολογιστικά;

Για το τελευτάιο ερώτημα , δεν θα έπρεπε να μας δίνεται κάποια πληροφορία για τον αισθητήρα , δηλαδή μια σχέση u,v ;
Εκτός αν ως είσοδο στο plant.p δώσουμε τον θόρυβο πριν περάσει από τον αισθητήρα.

Το u με τι ισουται ; Το παιρνουμε σαν random οπως το 1ο ερωτημα;

Κανονικά άμα κρίνω από την περσινή εκφώνηση θα έπρεπε να δίνεται μια σχέση που συνδέει τα u,v

Δοκίμασε η είσοδός σου να έχει αριθμό στηλών >= 2^10

Το σημα ν είναι ο λευκός θόρυβος σωστα ;

Ναι, σωστά! 

Θαύμα! Δούλεψε! Ευχαριστω!

Δεν μου έχει απαντήσει και στο μέιλ που ρώτησα αν και για τα υ, u

Παιζει να βρηκε καποιος κανενα αλγοριθμο για το ερωτημα 1; Γιατι δεν εχω βρει τιποτα μεχρι τωρα.

Μηπως απαντησε ?
Τι να κανουμε να τα παρουμε ίσα?δεν υπαρχει καμια πληροφορια για αυτο..

Εγώ χρησιμοποίησα τη σχέση της περσινής εκφώνησης πάντως (γιατί μπορώ  :D )

Στο δεύτερο ερώτημα εγώ έχω ένα πρόβλημα. Ενώ η συνέλιξη με toeplitz και circular βγαίνουν αρκετά κοντά μεταξύ τους, η συνέλιξη με conv βγαίνει εντελώς διαφορετική. Έχω δοκιμάσει με conv(y,x,'same') για να είναι ίδιου μήκους αλλά το αποτέλεσμα δεν είναι το ίδιο. Καμιά ιδέα κανείς?

τον Toeplitz πως τον δημιουργείς?
checkαρε εδώ το : Discrete-Time Convolution Using Toeplitz https://www.mathworks.com/help/matlab/ref/toeplitz.html?s_tid=doc_ta (https://www.mathworks.com/help/matlab/ref/toeplitz.html?s_tid=doc_ta)

Α οκ βγαίνει έτσι, εγώ χρησιμοποιούσα τον συμμετρικό toeplitz, θενξ!  ;)

Η εργασία πήρε άλλη μία μέρα παράταση.
Λήξη υποβολής εμπρόσθεσμων εργασιών   Τρίτη, 24 Απρίλιος 2018, 12:00 πμ

εννοει οτι θελει να δειξουμε τα αποτελεσματα μεταβαλλοντας το n και δινοντας μια δικια μας τιμη στο m ή να μεταβαλλονται και τα δυο ταυτοχρονα;

Μπορείς να βαλεις 3 4 τιμές στο m που να έχουν αρκετή διαφορά και κάθε φορά παίρνεις όλα τα n (μεταβλητό).
Ετσι καλύπτεις όλο το χώρο...

Για το α ερώτημα της εργασίας ήθελα μία βοήθεια. Bρήκα αυτό ψάχνοντας στο internet σχετικά για πολυπλοκότητα nlogn

http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html

Πρώτο πρόβλημα ήταν ότι ο toeplitz που μας δίνει δεν είναι τετραγωνικός. Για να το ξεπεράσω έκανα zero padding τον toeplitz ώστε να βγει τετραγωνικός και στη συνέχεια τον έκανα embed σε circulant όπως λέει το link. Bέβαια το y που παίρνω εάν έκανα το πολλαπλασιασμό κανονικά και το yf που παίρνω απο τη παραπάνω μέθοδο έχουν τεράστια διαφορά. Αν κάποιος έβγαλε άκρη, οποιαδήποτε βοήθεια σώζει ζωές  :D .

και εγώ με αυτό που έκανα βγαίνουν εντελώς διαφορετικά.. και πήρα μόνο τετραγωνικό  :P